📖 Chapter 2.6: Bit Operations

⏱ Estimated reading time: 55 minutes | Difficulty: 🟢 Beginner (USACO Bronze/Silver Essential)

Prerequisites

• Basic understanding of binary representation of integers
• Basic C++ syntax

🎯 Learning Objectives

After studying this chapter, you will be able to:

1. Understand the binary representation of an integer and see each bit as a small switch
2. Use the six basic bitwise operators for efficient integer operations
3. Check, set, clear, and flip individual binary bits
4. Use an integer as a set representation, also called a bitmask
5. Enumerate all subsets represented by an integer, which is the foundation of bitmask DP
6. Understand common bit tricks such as lowbit and fast power-of-two checks

2.6.1 Why Learn Bit Operations?

When a computer stores an integer, it does not store it as decimal digits like 0, 1, 2, 3... internally. Instead, it stores the number as a sequence of binary bits. For example:

Decimal 13 = Binary 1101

You can think of 1101 as four small light bulbs:

Position: 3 2 1 0
Binary:   1 1 0 1
Meaning:  on on off on

Each bit has its own value:

So 13 = 8 + 4 + 1.

Bit operations directly operate on these small light bulbs. Ordinary arithmetic such as addition, subtraction, multiplication, and division works on the whole number. Bit operations work on each internal bit of the number.

Typical applications in programming contests:

A Tiny Example: Why Can x & 1 Check Odd or Even?

Whether a number is odd only depends on the last binary bit:

12 = 1100, the last bit is 0, so it is even
13 = 1101, the last bit is 1, so it is odd

The binary representation of 1 has only the last bit set:

13 & 1
1101
0001
----
0001  -> the result is not 0, so 13 is odd

12 & 1
1100
0001
----
0000  -> the result is 0, so 12 is even

This is the mindset of bit operations: do not look at the whole number; focus only on the bit you care about.

2.6.2 Six Basic Bitwise Operators

Intuitive Memory Aids

AND  &: result is 1 only if both bits are 1 (intersection: keep what both have)
OR   |: result is 1 if at least one bit is 1 (union: keep what either has)
XOR  ^: result is 1 if the two bits are different (difference / flip)
NOT  ~: 0 becomes 1, and 1 becomes 0 (complement)

Compute One Bit at a Time, Not the Whole String at Once

A common beginner mistake is to treat 1100 & 1010 as an ordinary number calculation. In reality, it compares bits column by column:

  1100
& 1010
------
  1000

Look at each column from right to left:

Similarly, | means “turn on if at least one side is 1”, and ^ means “turn on only if the two sides are different”.

Left Shift and Right Shift: Moving the Whole Row of Switches

<< and >> do not change the value of each bit by itself. They move the whole row of binary bits to the left or to the right.

1       = 0001
1 << 1  = 0010 = 2
1 << 2  = 0100 = 4
1 << 3  = 1000 = 8

So 1 << k means: turn on only the k-th bit.

This is the foundation of almost all templates later:

1 << k

You can understand it as a small tool that selects only the k-th bit.

2.6.3 Common Bit Manipulation Templates

First remember one core tool:

1 << k

It represents a number where only the k-th bit is 1. The k-th bit is counted from right to left, starting at 0:

k:       3 2 1 0
1 << 0 = 0 0 0 1
1 << 1 = 0 0 1 0
1 << 2 = 0 1 0 0
1 << 3 = 1 0 0 0

Suppose x = 13 = 1101, and we want to operate on bit 2. We can first create the mask 1 << 2 = 0100. All later operations simply combine x with this mask.

1. Check Whether the k-th Bit Is 1

Problem: Given an integer x, how do we know whether its k-th bit is on?

bool check(int x, int k) {
    return (x >> k) & 1;
}

This code has two steps:

1. x >> k: move the k-th bit to the far right.
2. & 1: check whether the rightmost bit is 1.

Why move the target bit to the far right? Because the rightmost bit is the easiest one to check. If we apply & 1, we keep only the last bit and turn all other bits into 0.

Suppose:

x = 13 = 1101
k = 2

Bit 2 is the third bit from the right:

Position: 3 2 1 0
x:        1 1 0 1
             ↑
          bit 2

Computation:

x >> 2:
1101 >> 2 = 0011

Then & 1:
0011
0001
----
0001

The result is 1, so bit 2 of 13 is on.

If we check bit 1 instead:

x >> 1:
1101 >> 1 = 0110

Then & 1:
0110
0001
----
0000

The result is 0, so bit 1 is not on.

2. Set the k-th Bit to 1

Problem: How do we turn on one specific light? If it is already on, keep it on.

int set_bit(int x, int k) {
    return x | (1 << k);
}

The key here is |: if at least one side is 1, the result is 1.

So we first use 1 << k to create a mask where only the k-th bit is 1, then use | to turn that bit on.

Suppose:

x = 13 = 1101
k = 1
mask = 1 << 1 = 0010

Computation:

  1101
| 0010
------
  1111 = 15

Bit 1 was 0, and now it is turned on.

If that bit was already 1, nothing bad happens:

x = 13 = 1101
k = 2
mask = 0100

  1101
| 0100
------
  1101

Bit 2 was already 1, so it remains 1 after the set operation.

3. Set the k-th Bit to 0

Problem: How do we turn off one specific light? If it is already off, keep it off.

int clear_bit(int x, int k) {
    return x & ~(1 << k);
}

This code looks a little harder than setting a bit because it contains ~. Let us split it apart:

1. 1 << k: create a mask where only the k-th bit is 1.
2. ~(1 << k): flip the mask, so the k-th bit becomes 0 and all other bits become 1.
3. x & ~(1 << k): use & to keep all other bits while forcing the k-th bit to become 0.

Suppose:

x = 13 = 1101
k = 2

First create the mask:

1 << 2 = 0100

Flip it:

~0100 = ...1011

For easier observation, we only look at the lowest four bits:

1011

Then apply &:

  1101
& 1011
------
  1001 = 9

Bit 2 is turned off, while all other bits stay the same.

If bit k was already 0, clearing it will not change it:

x = 13 = 1101
k = 1
the lowest four bits of the flipped mask are 1101

  1101
& 1101
------
  1101

4. Flip the k-th Bit

Problem: How do we reverse one specific light? If it is on, turn it off; if it is off, turn it on.

int flip_bit(int x, int k) {
    return x ^ (1 << k);
}

Here we use ^. Its rule is: same gives 0, different gives 1.

A more useful way to remember it is:

some bit ^ 0: stays unchanged
some bit ^ 1: gets flipped

So x ^ (1 << k) means: only the k-th bit XORs with 1; all other bits XOR with 0. Therefore only the k-th bit changes.

Example 1: flip bit 1 from 0 to 1.

x = 13 = 1101
k = 1
mask = 0010

  1101
^ 0010
------
  1111 = 15

Example 2: flip bit 2 from 1 to 0.

x = 13 = 1101
k = 2
mask = 0100

  1101
^ 0100
------
  1001 = 9

So flipping does not always mean “make it 1”, and it does not always mean “make it 0”. It means: change the current state to the opposite state.

5. Check Whether a Number Is a Power of 2

Problem: How do we quickly check whether x is one of 1, 2, 4, 8, 16...?

bool is_power_of_two(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

First observe what powers of 2 look like in binary:

They all have one common property: there is exactly one 1 in the binary representation.

Now look at what happens to x - 1. Take x = 8 as an example:

x     = 1000
x - 1 = 0111

Apply &:

  1000
& 0111
------
  0000

The result is 0, which means 8 has only one 1, so it is a power of 2.

Now look at a number that is not a power of 2, such as 12:

x     = 1100
x - 1 = 1011

  1100
& 1011
------
  1000

The result is not 0, which means 12 has more than one 1, so it is not a power of 2.

Why do we also need x > 0? Because 0 is not a power of 2. Without this condition, 0 & -1 also gives 0, which would cause a wrong answer.

6. Get the Lowest Set Bit: lowbit

Problem: How do we find the first light that is on when scanning a number from right to left?

int lowbit(int x) {
    return x & (-x);
}

lowbit(x) does not return the position number. It returns the value represented by that bit.

For example:

x = 12 = 1100

Scanning from right to left:

Position: 3 2 1 0
x:        1 1 0 0
           ↑
     the rightmost 1 is at bit 2

The value of bit 2 is 4, so:

lowbit(12) = 4

Using two's complement:

Binary of 12:      0000 1100
-12 in complement: 1111 0100
12 & (-12):        0000 0100 = 4

This is very common in Fenwick trees. For now, you can remember that lowbit(x) gets the value represented by the rightmost 1 in x.

7. Clear the Lowest Set Bit

Problem: How do we delete the rightmost 1?

int clear_lowest(int x) {
    return x & (x - 1);
}

This uses the same core trick as the power-of-two check.

Suppose:

x = 12 = 1100
x - 1 = 11 = 1011

Computation:

  1100
& 1011
------
  1000 = 8

We can see that the rightmost 1 of x has been cleared.

Another example:

x = 10 = 1010
x - 1 = 9 = 1001

  1010
& 1001
------
  1000 = 8

What is this useful for? If we repeatedly clear the lowest set bit, we can count how many 1s are in a number.

8. Count the Number of 1 Bits: popcount

Problem: How do we know how many lights are on in the binary representation of an integer?

C++ provides a built-in function:

int count_ones(int x) {
    return __builtin_popcount(x);
}

For example:

x = 13 = 1101

There are three 1 bits, so:

count_ones(13) = 3

If we do not use the built-in function, we can manually implement it using the idea of clear_lowest:

int count_ones_manual(int x) {
    int cnt = 0;
    while (x) {
        x &= x - 1;
        cnt++;
    }
    return cnt;
}

Take x = 13 = 1101 as an example:

Round 1: 1101 -> 1100, cnt = 1
Round 2: 1100 -> 1000, cnt = 2
Round 3: 1000 -> 0000, cnt = 3

When the loop ends, all 1 bits have been cleared, so the original number had 3 ones.

Common Template Summary

We have now explained every function separately. In actual problem solving, you can treat the following functions as a small toolkit:

// ===== Single-bit operations (bit k, counted from 0) =====

// Check whether bit k is 1
bool check(int x, int k) { return (x >> k) & 1; }

// Set bit k to 1
int set_bit(int x, int k) { return x | (1 << k); }

// Set bit k to 0
int clear_bit(int x, int k) { return x & ~(1 << k); }

// Flip bit k (0 -> 1, 1 -> 0)
int flip_bit(int x, int k) { return x ^ (1 << k); }


// ===== Common tricks =====

// Check whether x is a power of 2 (and x > 0)
bool is_power_of_two(int x) { return x > 0 && (x & (x - 1)) == 0; }

// Get the lowest set bit (lowbit, core operation in Fenwick trees)
int lowbit(int x) { return x & (-x); }

// Clear the lowest set bit
int clear_lowest(int x) { return x & (x - 1); }

// Count the number of 1 bits in x (popcount)
int count_ones(int x) { return __builtin_popcount(x); }     // built-in function
// Or manually:
int count_ones_manual(int x) {
    int cnt = 0;
    while (x) { x &= x - 1; cnt++; }  // clear the lowest 1 each time
    return cnt;
}

Section Summary

2.6.4 Using Integers to Represent Sets (Bitmask)

When the number of elements N ≤ 30, we can use the N binary bits of an int to represent a set.

Encoding rule: element i is in the set ↔ bit i is 1.

Think of a Set as an Attendance Sheet

Suppose there are 5 students numbered 0, 1, 2, 3, 4. We can use 5 switches to show whether each student is selected:

Student ID: 4 3 2 1 0
Selected:   1 0 1 0 1

This means students {0, 2, 4} are selected. Written in binary, this is 10101, which is decimal 21.

The benefit is that one integer can store a whole set, and adding, removing, and checking elements can all be done in O(1).

// The set {0, 2, 4} is represented as:
// Binary: 10101 = 21

int S = 0;           // empty set
S = set_bit(S, 0);   // add element 0: S = 00001 = 1
S = set_bit(S, 2);   // add element 2: S = 00101 = 5
S = set_bit(S, 4);   // add element 4: S = 10101 = 21

// Check whether element 2 is in the set
bool has2 = check(S, 2);  // true

// Remove element 2
S = clear_bit(S, 2);      // S = 10001 = 17

// Set size
int size = __builtin_popcount(S);  // 2

Set Operations

int A = 0b1100;  // {2, 3}
int B = 0b1010;  // {1, 3}

int inter = A & B;    // intersection: 0b1000 = {3}
int unio  = A | B;    // union:        0b1110 = {1, 2, 3}
int diff  = A & ~B;   // difference A-B: 0b0100 = {2}
int xor_s = A ^ B;    // symmetric difference: 0b0110 = {1, 2}

These set operations correspond exactly to mathematical set operations:

For example, A = {2, 3} and B = {1, 3}:

Both A and B contain 3, so the intersection is {3}
A or B contains 1, 2, and 3, so the union is {1,2,3}
A contains 2 but B does not, so A-B is {2}
The elements that appear exactly once are 1 and 2, so the symmetric difference is {1,2}

2.6.5 Enumerating All Subsets

A set of N elements has 2^N subsets. We can enumerate them with for (int s = 0; s < (1 << n); s++).

Why 2^N? Because each element has only two choices:

Do not choose this element -> 0
Choose this element        -> 1

If there are 3 elements, each element has two possible states, so the total number of subsets is:

2 × 2 × 2 = 8

That is 2^3 subsets.

First Look at the Complete Example for n = 3

So enumerating integers from 0 to 2^n - 1 is really enumerating every combination of switches, which means every subset.

// Enumerate all subsets of n elements
void enumerate_subsets(int n) {
    for (int s = 0; s < (1 << n); s++) {
        cout << "subset " << s << " (binary " << bitset<4>(s) << "): {";
        for (int i = 0; i < n; i++) {
            if (check(s, i)) cout << i << " ";
        }
        cout << "}\n";
    }
}
// enumerate_subsets(3) prints 2^3 = 8 subsets

Enumerating All Subsets of a Given Set S

Sometimes we are not enumerating all subsets of the universal set {0,1,2,...,n-1}. Instead, we need to enumerate all subsets of a given set S.

For example:

S = 10110 = {1,2,4}

We only want to enumerate subsets formed from {1,2,4}. Elements 0 and 3 must not appear.

// Enumerate all non-empty subsets of S (time: O(3^n), see explanation below)
for (int sub = S; sub > 0; sub = (sub - 1) & S) {
    // process subset sub
    // ...
}
// Idea: sub = (sub - 1) & S decreases within the range of S and skips bits not in S

Why Does sub = (sub - 1) & S Stay Inside S?

sub - 1 changes the binary representation and may create some 1s in positions that do not belong to S. Applying & S again is like using S as a filter: only positions that are originally 1 in S can remain.

For S = 10110, the enumeration roughly goes like this:

10110
10100
10010
10000
00110
00100
00010

Every step uses only bits allowed by S.

2.6.6 Practice Examples: Bitmask + Bit Operations

Previously, we learned the tools. Now we will put those tools into problems. When solving a bit operation problem, think in this order:

1. What does each bit represent? Is it an element, a city, or a switch?
2. What do 1 and 0 mean? For example, 1 means selected and 0 means not selected.
3. Which bit operation matches the action? Add with |, remove with & ~, check with & or right shift.
4. How many states are there? If there are n switches, there are usually 2^n states.

Example: Subset Sum Problem

Given N numbers (N ≤ 20), count how many subsets have sum exactly equal to target.

Why can we brute force?

When N ≤ 20, there are 2^20 = 1,048,576 subsets, which is about one million. For each subset, scanning at most 20 numbers gives about twenty million operations, which is usually acceptable in C++.

State design:

• s is a binary set.
• If bit i of s is 1, then a[i] is selected.
• Enumerating all s means enumerating all possible choices.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    
    int ans = 0;
    for (int s = 0; s < (1 << n); s++) {
        int sum = 0;
        for (int i = 0; i < n; i++)
            if (check(s, i)) sum += a[i];
        if (sum == target) ans++;
    }
    
    cout << ans << "\n";
}
// Complexity: O(2^N × N). For N=20, about 2×10^7 operations, acceptable.

Example: Traveling Salesman Problem (Bitmask DP Basics)

There are N cities (N ≤ 20). Starting from city 0, visit every city exactly once, return to city 0, and find the shortest route.

This problem is harder than subset sum because it needs to record not only “which cities have been visited” but also “which city we are currently at”.

State design:

dp[mask][v]

Meaning:

• mask represents the set of cities already visited.
• v represents the current city.
• dp[mask][v] is the shortest distance under this situation.

For example, mask = 01011 means cities {0,1,3} have been visited. If v = 3, it means we are currently at city 3.

Transition idea:

If we are currently at city u, the next step can go to an unvisited city v. Then:

new_mask = mask | (1 << v);

This means marking city v as visited.

#include <bits/stdc++.h>
using namespace std;

int n;
int dist[20][20];
int dp[1 << 20][20];  // dp[mask][v] = shortest distance after visiting mask and ending at v

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> dist[i][j];
    
    // initialization
    for (auto& row : dp) fill(row, row + n, INT_MAX / 2);
    dp[1][0] = 0;  // start from city 0, mask=1 means only city 0 has been visited
    
    // enumerate all states
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (dp[mask][u] == INT_MAX / 2) continue;
            if (!check(mask, u)) continue;
            
            // try moving to an unvisited city v
            for (int v = 0; v < n; v++) {
                if (check(mask, v)) continue;  // already visited
                int new_mask = set_bit(mask, v);
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    
    // after all cities are visited (mask = (1<<n)-1), return to city 0
    int ans = INT_MAX;
    int full = (1 << n) - 1;
    for (int u = 1; u < n; u++)
        ans = min(ans, dp[full][u] + dist[u][0]);
    
    cout << ans << "\n";
    // Complexity: O(2^N × N^2). For N=20, about 4×10^8 operations, which is large.
    // N=15~18 is usually more practical.
}

⚠️ Common Mistakes

💪 Exercises

🟢 Problem 1: Parity Statistics

Given an integer x, output the number of 1 bits in its binary representation, also called popcount, and whether it is a power of 2.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x; cin >> x;
    cout << __builtin_popcount(x) << "\n";
    cout << (x > 0 && (x & (x-1)) == 0 ? "power of 2" : "not power of 2") << "\n";
}

🟢 Problem 2: Bit Flipping

Given an integer x and an array of positions k[], flip all these bits of x and output the result.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x, m; cin >> x >> m;
    while (m--) {
        int k; cin >> k;
        x ^= (1 << k);  // XOR flips bit k
    }
    cout << x << "\n";
}

🟡 Problem 3: Subset Enumeration

Given N numbers (N ≤ 20), count all subsets whose sum is even.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    
    int cnt = 0;
    for (int s = 0; s < (1 << n); s++) {
        int sum = 0;
        for (int i = 0; i < n; i++)
            if ((s >> i) & 1) sum += a[i];
        if (sum % 2 == 0) cnt++;
    }
    cout << cnt << "\n";
    // The answer is always 2^(n-1) if there is at least one odd number.
}

🔴 Problem 4: Maximum XOR Subset

Given N numbers (N ≤ 20), choose a non-empty subset so that the XOR sum of all numbers in the subset is maximized. Output this maximum value.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    
    int ans = 0;
    for (int s = 1; s < (1 << n); s++) {
        int xor_sum = 0;
        for (int i = 0; i < n; i++)
            if ((s >> i) & 1) xor_sum ^= a[i];
        ans = max(ans, xor_sum);
    }
    cout << ans << "\n";
}

🔴 Problem 5: USACO Bronze Style — Cow Gymnastics (Bit Operation Version)

There are N cows (N ≤ 20) and K training rounds. In each round, the cows are listed from rank 1 to rank N. A pair of cows (i, j) is called consistent if cow i ranks before cow j in every round. Use bit operations to count how many cow pairs are consistent.

Input: The first line contains K and N. The next K lines each contain a permutation of integers from 1 to N, representing the ranking order in that round.

Sample Input:

3 4
4 1 2 3
4 1 3 2
4 2 1 3

Sample Output: 4

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int K, N;
    cin >> K >> N;

    // before[i]'s bit j = whether cow j is always before cow i in all processed rounds
    vector<int> before(N, (1 << N) - 1);  // initially all 1s, then AND round by round

    for (int round = 0; round < K; round++) {
        // ranking[0] = cow ranked 1st, etc.
        vector<int> ranking(N);
        for (int p = 0; p < N; p++) cin >> ranking[p];

        // mask records cows already seen in this round, meaning cows ranked before current cow
        int mask = 0;
        for (int p = 0; p < N; p++) {
            int cow = ranking[p] - 1;  // convert to 0-indexed
            before[cow] &= mask;       // AND with cows before this cow in current round
            mask |= (1 << cow);        // add current cow to the seen set
        }
    }

    int ans = 0;
    for (int i = 0; i < N; i++)
        ans += __builtin_popcount(before[i]);
    cout << ans << "\n";
}

💡 Chapter connection: Bit operations are the foundation of bitmask DP (advanced DP in Chapter 6.3), and they are also used in the lowbit operation of Fenwick trees (Chapter 5.7). After mastering this chapter, you will be able to understand most bit operation tricks in competitive programming code.

Chapter Summary

• Bits are switches: each bit has only two states, 0 and 1.
• 1 << k is the core tool: it creates a mask where only bit k is selected.
• Single-bit operations follow fixed patterns: checking, setting, clearing, and flipping correspond to different bit operations.
• Bitmasking means storing a set in an integer: bit i is 1 if element i is selected.
• Subset enumeration means enumerating switch combinations: numbers from 0 to (1 << n) - 1 cover every choose/not-choose plan.
• Do not just memorize code: when solving a problem, first ask “what does each bit represent?”, then choose the proper bit operation.