Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DSA

Bit Manipulation

Computers store integers in binary. Working directly on bits gives very fast, very short solutions to some problems.

13 in binary is 1101 = 8 + 4 + 0 + 1. Bits are numbered from the right, starting at 0.

Operators

Operator C++ Rule Example (12 = 1100, 10 = 1010)
AND a & b 1 if both are 1 1000 = 8
OR a | b 1 if either is 1 1110 = 14
XOR a ^ b 1 if they differ 0110 = 6
NOT ~a flips every bit ~12 = -13 (two's complement)
Left shift a << k multiply by 2ᵏ 3 << 2 = 12
Right shift a >> k divide by 2ᵏ (floor, for positives) 12 >> 2 = 3

XOR properties (the most useful)

Single number (every element appears twice except one):

int singleNumber(vector<int>& a) {
    int x = 0;
    for (int v : a) x ^= v;     // pairs cancel out
    return x;
}

Missing number in 0..n: XOR all indices and values — what remains is the missing one. Swap without a temp: a ^= b; b ^= a; a ^= b; (fun fact; don't use it in real code).

Single-bit tricks

Task Code
Is bit i set? (x >> i) & 1
Set bit i x | (1 << i)
Clear bit i x & ~(1 << i)
Toggle bit i x ^ (1 << i)
Lowest set bit x & (-x)
Remove lowest set bit x & (x - 1)
Is power of two? x > 0 && (x & (x - 1)) == 0
Is odd? x & 1

Count set bits

int countBits(int x) {           // Brian Kernighan: loops once per set bit
    int c = 0;
    while (x) { x &= x - 1; c++; }
    return c;
}
// built-in: __builtin_popcount(x), __builtin_popcountll(x) for long long

Bitmask subsets

A number from 0 to 2ⁿ − 1 can represent a subset of n items: bit i = 1 means item i is chosen.

void allSubsets(vector<int>& a) {
    int n = a.size();
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++)
            if (mask & (1 << i)) cout << a[i] << " ";
        cout << "\n";
    }
}

Bitmask DP (e.g. travelling salesman for n ≤ 20) uses the mask as part of the state.

Two's complement (negative numbers)

-x = ~x + 1. For 8 bits, -1 is 11111111. This is why ~12 = -13.

Gotchas

Classic problems

Problem Trick
Single number XOR all
Single number II (others appear 3 times) count each bit mod 3
Two single numbers XOR, split by lowest set bit
Missing number XOR indices and values
Number of 1 bits / counting bits x & (x-1), dp[i] = dp[i >> 1] + (i & 1)
Power of two / four x & (x-1)
Reverse bits shift out and in 32 times
Subsets bitmask from 0 to 2ⁿ − 1
Maximum XOR of two numbers trie of bits

Practise in the Bit Manipulation section.

Interview one-liners

More DSA notes