Lesson 4 · Problem-solving methods

Bit Manipulation

Bit manipulation works on a number's binary representation directly. A handful of identities replace loops with single instructions, turn sets into integers, and answer questions in O(1) that would otherwise need extra memory.

The Six Operators

Bitwise operators act on the individual binary digits of an integer rather than on its value. There are six, and each has a characteristic use worth attaching to it rather than memorising the truth table alone.

AND (&) gives 1 only where both operands have 1. Its job is masking — x & mask keeps the bits the mask selects and zeroes everything else. Testing whether bit i is set is x & (1 << i).

OR (|) gives 1 where either has 1. Its job is setting bits: x | (1 << i) turns bit i on and leaves the rest alone.

XOR (^) gives 1 where the operands differ. Its job is toggling: x ^ (1 << i) flips bit i. XOR has the properties that make the tricks below work — x ^ x = 0, x ^ 0 = x, and it is both commutative and associative.

NOT (~) inverts every bit. In two's complement ~x equals -x - 1, which is worth knowing because it explains several identities that otherwise look arbitrary.

Left shift (<<) moves bits toward the high end, filling with zeros; x << k multiplies by 2^k. Right shift (>>) moves them down; for non-negative values x >> k divides by 2^k, discarding the remainder.

Right shift on negative numbers is where languages diverge and where portable code goes wrong. An arithmetic shift copies the sign bit, preserving the sign; a logical shift fills with zeros, turning a negative number positive. C and C++ use arithmetic shifting for signed types; Java provides both, >> arithmetic and >>> logical; JavaScript's >>> likewise. Shifting by an amount greater than or equal to the type's width is undefined behaviour in C and C++, and in Java the shift count is silently taken modulo 32 or 64 — so 1 << 32 is 1, not zero, which surprises people.

The operators and their characteristic use
Operator	Effect	Idiom
`&`	1 where both are 1	Mask — test a bit: `x & (1<<i)`
`\|`	1 where either is 1	Set a bit: `x \| (1<<i)`
`^`	1 where they differ	Toggle: `x ^ (1<<i)`; `x^x = 0`
`~`	Invert every bit	`~x == -x - 1` in two's complement
`<<`	Shift up, zero-fill	Multiply by 2^k
`>>`	Shift down	Divide by 2^k — sign handling varies

AND masks, OR sets, XOR toggles, NOT inverts
Clearing bit i is x & ~(1 << i)
Arithmetic and logical right shifts differ on negative values
Shifting by ≥ the type width is undefined in C, and wraps in Java

The Identities Worth Memorising

Two expressions account for a large share of bit-manipulation problems, and understanding why they work makes them reconstructable rather than memorised.

n & (n − 1) clears the lowest set bit. Subtracting 1 flips that lowest 1 to 0 and turns every 0 below it into 1; ANDing with the original keeps only the bits above, so the lowest 1 disappears. For n = 12 (1100), n−1 is 1011, and the AND gives 1000.

Two consequences follow immediately. Counting set bits — Brian Kernighan's algorithm — repeats the operation until n reaches zero, counting iterations. It runs once per set bit rather than once per bit position, so a number with three ones costs three iterations regardless of width. And testing a power of two is n > 0 && (n & (n-1)) == 0, since a power of two has exactly one set bit and clearing it leaves zero.

n & (−n) isolates the lowest set bit, giving its value rather than removing it. In two's complement -n is ~n + 1; inverting flips the lowest 1 to 0 and the zeros below to 1, and adding one carries through them to land exactly on that position. So n and −n share exactly one bit. For n = 12 this yields 4. This is the lowbit operation that drives the Fenwick tree's traversal.

A handful of others are worth recognising. x ^ y swaps two variables without a temporary, using three XORs — a classic that is slower than a temporary on modern hardware and fails when both operands are the same variable, so it is trivia rather than technique. x & (x-1) == 0 as above. And (x >> i) & 1 extracts bit i as 0 or 1.

Most languages provide these as builtins, and using them is better than hand-rolling: __builtin_popcount in GCC, Integer.bitCount in Java, bin(x).count('1') or int.bit_count() in Python. They compile to a single POPCNT instruction on modern CPUs.

n & (n−1) clears the lowest set bit — counts bits in O(set bits)
Power of two test: n > 0 && (n & (n−1)) == 0
n & (−n) isolates the lowest set bit — the Fenwick tree's lowbit
Prefer builtin popcount; it compiles to one instruction

XOR and Its Cancellation

XOR's usefulness comes from three properties: x ^ x = 0, x ^ 0 = x, and it is commutative and associative. Together these mean XOR-ing a collection makes paired values cancel regardless of their order, leaving only what appears an odd number of times.

Single number. Given an array where every value appears twice except one, XOR everything together. The pairs cancel to zero and the answer remains — O(n) time, O(1) space, no hash set and no sorting. This is the canonical demonstration and the reason XOR appears in interviews at all.

Missing number. For an array holding 0 to n with one value absent, XOR all the indices and all the values together. Every present number is XOR-ed twice and cancels; the missing one appears only once and survives. Unlike the sum-based solution, this cannot overflow, which is a genuine advantage on large inputs.

Two single numbers. When exactly two values appear once, XOR-ing everything gives a ^ b, which is non-zero. Take any set bit of that result — conveniently the lowest, via n & (-n) — and note that a and b differ at that position. Partition the array by that bit and XOR each half separately; each half contains one of the two answers along with complete pairs. This partition-by-a-differing-bit step is the insight the problem is testing.

Finding a duplicate or a swapped pair uses the same cancellation, and the general pattern is: whenever elements pair off and you need what does not pair, XOR is the O(1)-space tool.

One caution worth stating: XOR only detects values appearing an odd number of times. A value appearing three times survives just as a single one would, so the technique needs the problem to guarantee exact pairing. Problems where values appear three times require a different approach — counting bits modulo 3 across all positions.

x ^ x = 0 makes pairs cancel in any order
Single number and missing number both fall out in O(1) space
XOR-based missing number cannot overflow, unlike the sum method
Two singles: split the array by a bit where they differ

Key reference

Terms, operations, and practical uses

Core vocabulary

BitmaskAn integer used to represent a set of boolean flags or items, where each bit corresponds to one item's presence (1) or absence (0).
Bitwise XOR (^)An operation that outputs 1 only if the two input bits are different. Useful for toggling bits.
Shift (<<, >>)Moving bits to the left (multiplying by powers of 2) or right (dividing by powers of 2).

Common operations

Set a bitUse OR: mask | (1 << i) sets the i-th bit to 1.
Clear a bitUse AND with NOT: mask & ~(1 << i) sets the i-th bit to 0.
Check a bitUse AND: (mask & (1 << i)) != 0 checks if the i-th bit is 1.

Advanced tricks

Isolate Lowest Set BitThe expression x & -x returns the value of the lowest set bit in x.
Clear Lowest Set BitThe expression x & (x - 1) turns off the lowest set bit in x.
Check Power of 2A number is a power of 2 if x > 0 and (x & (x - 1)) == 0.

Implementation

Count the set bits in 12 with n & (n − 1)

def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1          # clear the lowest set bit
        count += 1
    return count

print(count_set_bits(12))   # 2

#include <iostream>
using namespace std;
int countSetBits(int n) {
    int count = 0;
    while (n) {
        n &= n - 1; // clear the lowest set bit
        count++;
    }
    return count;
}
int main() {
    cout << countSetBits(12) << '\n'; // 2
}

class Main {
    static int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            n &= n - 1; // clear the lowest set bit
            count++;
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(countSetBits(12)); // 2
    }
}

Watch it run

Step through it

Running on n = 12 (binary 1100)

Output

Read all 9 Steps

Start with n = 12 12 is 1100 in binary, so two bits are set. A naive loop tests all 32 bit positions; Brian Kernighan's trick visits only the set ones, making it O(number of set bits).
Compute n − 1 = 11 Subtracting one flips the lowest set bit to 0 and turns every bit below it into 1, so 1100 becomes 1011. This single identity is what the whole algorithm rests on.
AND them: 1100 & 1011 Column by column the two patterns agree only at the top bit. The lowest set bit of n is gone, and the bits n − 1 turned on were never set in n, so they vanish too.
n = 8, count = 1 One set bit was removed, so increment the counter. n is now 1000 — the original value with its rightmost 1 cleared and nothing else touched.
n is not zero, so loop again The loop condition is `while n`, and 8 is truthy, so a second pass runs. The number of passes equals the number of set bits, never the width of the integer.
Compute n − 1 = 7 8 − 1 = 7 is 0111. Again the lowest set bit clears and every position below it fills with ones — the borrow ripples all the way down.
AND them: 1000 & 0111 No column holds a 1 in both operands, so every result bit is 0 and n becomes 0000.
n = 0, count = 2 The second set bit is accounted for. n has reached zero, the loop condition fails, and the walk ends after exactly two iterations for two set bits.
Answer: 12 has 2 set bits Return 2. The same identity answers a second question for free: if n & (n − 1) is 0 on the very first pass, n had exactly one set bit and is therefore a power of two.

Integers as Sets

A bitmask treats an integer as a set of up to 64 elements, with bit i meaning element i is present. This is the most practically useful application, and it turns set operations into single machine instructions.

Union is a | b. Intersection is a & b. Difference is a & ~b. Symmetric difference is a ^ b. Membership is (mask >> i) & 1. Size is popcount(mask). Each is one instruction, against a hash set's hashing, allocation and pointer chasing.

Iterating all subsets of a set of n elements is a loop from 0 to 2^n − 1, with each value's bits naming a subset. Iterating the subsets of a specific mask uses the idiom for (int s = mask; s > 0; s = (s-1) & mask), which enumerates them without visiting anything outside the mask — a standard trick worth knowing.

The major algorithmic use is bitmask dynamic programming, where the DP state includes a set of already-processed items. The travelling salesman problem over n cities has state (currentCity, visitedMask), giving O(2ⁿ · n²) — exponential, but tractable to about n = 20, where the brute-force n! is hopeless past n = 12. Assignment problems and set-cover variants use the same shape.

Practical uses are broader than the algorithmic ones. Permission flags — read, write, execute — pack into one integer, which is exactly what Unix file modes are. Feature flags and option sets do the same. A chess engine represents the board as bitboards, one 64-bit integer per piece type, so move generation becomes shifts and masks.

Two limits to state. The set size is capped by the integer width — 64 elements — beyond which you need an array of words or the language's bitset type. And bitmask code is dense and error-prone: an off-by-one in a shift produces a silently wrong answer. Naming the masks with constants rather than writing raw literals is worth the small effort.

Union |, intersection &, difference & ~, size popcount
Enumerate submasks with s = (s-1) & mask
Bitmask DP solves TSP in O(2ⁿ·n²) — usable to about n = 20
Capped at the integer width; use a bitset beyond 64 elements