On this page

Bit Manipulation

Bit manipulation is the art of operating directly on binary representations of numbers. These techniques unlock constant-time solutions to problems that would otherwise require extra space or multiple passes. In interviews, bit manipulation questions test your understanding of how numbers are stored at the machine level. In production, bitwise operations power bloom filters, feature flags, permission systems, and high-performance networking code.

This lesson is part of Module 5 (Paradigms) of DSA: Zero to Mastery. It starts from "what is a bit?" and ends with tools that competitive programmers use every week: enumerating all submasks of a mask in total, jumping to the next combination with Gosper's hack, Gray codes, the "three times" single-number state machine, and bitsets that make an inner loop 64 times faster. Every trick comes with a proof — a short argument that explains why it works — because tricks you can prove are tricks you can adapt.

Why this exists

A computer stores a number as a row of switches, each off (0) or on (1). Bitwise operators act on those switches directly, a whole machine word (32 or 64 of them) at a time, in one CPU cycle.

That gives you three superpowers:

  1. Compact sets. A 64-bit word holds the answers to 64 yes/no questions. Membership is one AND, union is one OR, and each of the subsets of 20 items fits in one int. That is the foundation of Bitmask DP and SOS DP.
  2. Word-level parallelism. One AND on 64-bit words performs 64 logical ANDs at once. Bitsets, chess engines and string-search algorithms such as Shift-And exploit this to get a factor of about 64 for free.
  3. Algebra you can exploit. XOR behaves like addition where . That one fact solves "find the element without a twin", builds Gray codes, powers RAID-5 parity and the XOR trie for maximum-XOR queries.

Many of these tricks were collected in the MIT memo HAKMEM (1972); Henry S. Warren's Hacker's Delight (2nd ed., 2012) and Knuth's TAOCP Vol. 4A §7.1.3 are the standard references.

Pattern triggers

If the problem says or has…Think of…
"every element appears twice except one"XOR everything: pairs cancel
"appears three times except one"Count each bit mod 3, or the ones/twos state machine
"two elements appear once, the rest twice"XOR all, split on the lowest differing bit
"is a power of two", "exactly one bit set"n > 0 && (n & (n - 1)) == 0
"number of 1 bits", "Hamming weight", "Hamming distance"Popcount (builtin, Kernighan, SWAR); distance = popcount(a ^ b)
items and "choose any subset"Bitmask enumeration over 0 .. 2^n - 1
"for every mask, look at all its submasks"for (s = m; s; s = (s - 1) & m), total
"all subsets of size exactly "Gosper's hack
"sequence where neighbours differ in one bit"Gray code i ^ (i >> 1)
"maximum XOR of two numbers / of a subarray"Greedy bit-by-bit with a hash set or an XOR trie
"each letter appears an even number of times"Prefix XOR of a 26-bit parity mask
"add without using +", "multiply by a power of two"a + b = (a ^ b) + 2(a & b), shifts
Subset-sum / reachability with values up to ~Bitset: reach |= reach << w
Flags, permissions, feature toggles stored in one integerOR to set, AND-NOT to clear, AND to test

The meta-trigger: the objects are small sets, parities, or yes/no answers, and you need to combine many of them quickly.

Binary Number Fundamentals

Every integer is stored as a sequence of bits. In a 32-bit system:

The rightmost bit is the least significant bit (LSB), the leftmost is the most significant bit (MSB).

DecimalBinary (8-bit)Hex
0000000000x00
1000000010x01
5000001010x05
10000010100x0A
255111111110xFF

Place value from first principles

In decimal, 305 means . Binary is the same idea with two instead of ten: each position (a bit, "binary digit") is worth twice the one to its right. We number the positions from the right starting at 0, so bit is worth .

Bit position 76543210
Worth 1286432168421
Bits of 4200101010

So . Two facts fall out immediately: bit 0 is the parity (every other position is worth an even amount), and shifting left doubles the number (as long as nothing falls off the top). A word is the fixed number of bits the machine handles at once — usually 32 or 64. A mask is a number built on purpose to select certain bits, like 0b00001111 for the low four.

Unsigned integers and their ranges

An unsigned integer of width bits uses every bit for magnitude. It can hold to . Arithmetic wraps around modulo : in 8 bits, , like a car odometer rolling over.

Width Unsigned rangeSigned (two's complement) rangeTypical types
80 … 255−128 … 127uint8_t, Java byte (signed only)
160 … 65,535−32,768 … 32,767uint16_t, Java short, char (unsigned 16)
320 … 4,294,967,295−2,147,483,648 … 2,147,483,647uint32_t, Java int, JS bitwise operands
640 … 18,446,744,073,709,551,615−9,223,372,036,854,775,808 … 9,223,372,036,854,775,807uint64_t, Java long

Two's complement from first principles

How do you store negative numbers with only 0s and 1s? Early machines tried sign-magnitude and ones' complement; both have two zeros (+0 and −0) and need special adder hardware. Every modern CPU uses two's complement, and C++20 made it mandatory for signed integers (proposal P1236).

The idea is the odometer. In 4 bits, counting down from 0 wraps to 1111. So we simply call 1111 "−1", 1110 "−2", and so on. Formally, in bits:

Equivalently, the top bit has negative weight: a -bit pattern means

Here is every 4-bit pattern:

PatternUnsigned valueTwo's complement valuePatternUnsigned valueTwo's complement value
00000010008−8
00011110019−7
001022101010−6
001133101111−5
010044110012−4
010155110113−3
011066111014−2
011177111115−1

Read the table and notice:

  • The top bit is the sign. Every negative number starts with 1.
  • There is one zero, and one extra negative: the range is −8…7, not −7…7. The lonely 1000 (−8) is the minimum, often written INT_MIN. Its negation does not fit: wraps back to 1000. This is why abs(INT_MIN) and -INT_MIN are classic bugs.
  • Addition needs no special case. The adder just adds the patterns modulo : is 1101 + 0101 = 1 0010; drop the carry out of bit 3 and you get 0010 = 2. Signed and unsigned addition are the same circuit.

How to negate by hand. Flip every bit, then add 1. Why? Flipping every bit of gives , because x + ~x is all ones (). Adding 1 gives , which is exactly the definition of . Example: 5 = 0101 → flip → 1010 → +1 → 1011 = −5. ✓

That same identity proves the rule quoted later in this lesson:

Sign extension. Widening a signed value copies the sign bit into the new top bits: 1111 1011 (−5 in 8 bits) becomes 1111 … 1111 1011 (−5 in 32 bits). Java's byte is signed, so write b & 0xFF to get 0…255.

Python is different. Python integers have no fixed width. Conceptually, a Python int is two's complement with infinitely many bits: non-negative numbers have infinitely many leading 0s, negative numbers infinitely many leading 1s. So ~5 == -6, -5 & 0xFF == 251 (the low 8 bits of −5), and bin(-5) prints '-0b101' (sign and magnitude, not the bit pattern). To get a 32-bit view of a Python int, mask with & 0xFFFFFFFF.

Hex and octal

One hex (base-16) digit is exactly 4 bits (A = 1010, F = 1111); one octal digit is exactly 3 bits. So 0x55555555 is 0101 0101 … (every even bit), 0x33333333 is 0011 0011 … and 0x0F0F0F0F is 0000 1111 … — masks you will meet in SWAR popcount. Octal survives mainly in Unix permissions: 0754 is 111 101 100.

Bitwise Operators

Every bitwise operator works on each bit position independently (shifts excepted). So one truth table describes the whole operator:

a & b (AND)a | b (OR)a ^ b (XOR)~a (NOT)
000001
010111
100110
111100

If you think of a number as a set of bit positions (bit set ⇔ element in the set), then AND is intersection, OR is union, XOR is symmetric difference, NOT is complement, and a & ~b is set difference .

AND (&)

Returns 1 only if both bits are 1. Used for masking and clearing bits.

OR (|)

Returns 1 if either bit is 1. Used for setting bits.

XOR (^)

Returns 1 if the bits differ. Used for toggling and finding unique elements.

Key XOR properties:

  • (self-cancellation)
  • (identity)
  • (commutative)
  • (associative)

Why these hold. On one bit, XOR is addition modulo 2: , , . Addition mod 2 is commutative and associative, 0 is its identity, and every bit is its own inverse (). Because XOR acts on each position independently, all four laws lift from single bits to whole words. In algebra language, -bit words under XOR form a group in which every element is its own inverse. Consequences you will use:

  • — XORing the same value twice undoes it. (This is why XOR "encryption" with a key is reversible, and why it is weak: when the key is reused.)
  • The order of a long XOR chain does not matter, so anything that appears an even number of times vanishes.
  • If then — you can "solve" XOR equations by XORing both sides.

NOT (~)

Flips all bits. In two's complement: .

Left Shift (<<)

Shifts bits left, filling with zeros. Equivalent to multiplying by .

Right Shift (>>)

Shifts bits right. Arithmetic right shift preserves the sign bit. Equivalent to integer division by .

graph LR
    subgraph "Operator Summary"
        AND["AND &<br/>Mask / Clear bits"]
        OR["OR |<br/>Set bits"]
        XOR["XOR ^<br/>Toggle / Find unique"]
        NOT["NOT ~<br/>Flip all bits"]
        SHL["<< Shift Left<br/>Multiply by 2^k"]
        SHR[">> Shift Right<br/>Divide by 2^k"]
    end

Clarification: "multiply" and "divide" have fine print

  • n << k equals only while the result still fits in the word. In 32-bit arithmetic 1 << 31 is already negative and 1 << 32 is not in any of Java, C++ or JavaScript (see the table below).
  • An arithmetic right shift computes — it rounds toward . But / in Java, C++ and JavaScript's Math.trunc(a / b) rounds toward zero. They agree for and disagree for negative odd values: -21 >> 2 is −6, while -21 / 4 is −5 in Java and C++. Python's // also floors, so in Python -21 >> 2 == -21 // 4 == -6.

Shifts in each language: signed vs unsigned

A logical right shift fills the vacated top bits with 0 (treats the word as unsigned). An arithmetic right shift fills them with copies of the sign bit (keeps negative numbers negative). Languages expose these differently, and this is where most cross-language bit bugs come from.

QuestionPythonJavaC++JavaScript / TypeScript
Integer widthUnboundedint 32, long 64Fixed by type (int is 32 on all mainstream platforms)Bitwise ops convert operands to 32-bit signed (ToInt32); >>> converts to 32-bit unsigned
>> on negativesArithmetic (floor)ArithmeticArithmetic for signed types since C++20; implementation-defined before (GCC/Clang/MSVC: arithmetic)Arithmetic on 32-bit
Logical right shiftNo operator: mask first, (x & 0xFFFFFFFF) >> k>>>Shift an unsigned type>>> (result is 0 … 2³²−1)
-21 >> 2−6−6−6−6
32-bit logical -21 >>> 2(-21 & 0xFFFFFFFF) >> 2 = 10737418181073741818uint32_t(-21) >> 2 = 10737418181073741818
1 << 3242949672961 (shift count masked to 5 bits: 32 & 31 = 0)Undefined behaviour (count ≥ width)1 (count masked to 5 bits)
1 << 312147483648−21474836481u << 31 is 2147483648; for int, defined since C++14 (gives INT_MIN), but prefer unsigned−2147483648
Signed overflow, e.g. INT_MAX + 1Never overflowsWraps (defined)Undefined behaviourNot an integer op; (2**31) | 0 gives −2147483648
Left shift of a negativeFine (-3 << 1 == -6)Fine (wraps)UB before C++20, defined (modular) sinceFine on 32-bit
64-bit bit opsNativelong, 1L << 40, Long.bitCountuint64_t, 1ULL << 40BigInt: 1n << 40n (no >>> for BigInt)

Three rules keep you safe:

  1. C++: do bit manipulation on unsigned types. Unsigned arithmetic wraps modulo ; signed overflow is undefined behaviour, so the optimizer may assume it never happens and delete your checks. Write 1ULL << i when i can reach 31.
  2. Java: use >>> for "unsigned", and 1L << i for 64-bit masks — 1 << 40 silently equals 1 << 8 = 256.
  3. JavaScript: bitwise operators work on 32-bit integers. x | 0 truncates to signed 32-bit; x >>> 0 reinterprets as unsigned (-1 >>> 0 === 4294967295). Use BigInt for wider masks.

Common Tricks

Almost every trick in this section rests on one picture. Write any non-zero as

where the 1 is the lowest set bit of (at position ), the zeros below it are its trailing zeros, and is whatever bits sit above. Now look at what subtracting 1 and negating do to this picture:

ExpressionBitsWhy
definition
subtracting 1 borrows through the trailing zeros, turning them to 1s and the lowest 1 to 0
flip everything
adding 1 carries through the trailing 1s
the lowest set bit is cleared, is kept
; only the lowest set bit survives
a mask of the lowest set bit and everything below
trailing zeros filled with 1s

A concrete trace with in 8 bits ($P = $ 0010, ):

Expression8-bit patternDecimal
x0010110044
x - 10010101143
x & (x - 1)0010100040
-x11010100−44
x & -x000001004
graph LR
    X["x = P 1 000"] -->|"subtract 1"| XM["x-1 = P 0 111"]
    X -->|"flip, add 1"| NX["-x = ~P 1 000"]
    XM -->|"AND with x"| C["x & (x-1) = P 0 000 (lowest 1 cleared)"]
    NX -->|"AND with x"| L["x & -x = 0 1 000 (lowest 1 isolated)"]

1. Check if Power of 2

A power of 2 has exactly one set bit: . Subtracting 1 flips all bits below: . AND them together and you get zero.

TypeScript:

function isPowerOfTwo(n: number): boolean {
  return n > 0 && (n & (n - 1)) === 0;
}

Python:

def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

Proof. By the picture above, n & (n - 1) equals , which is zero exactly when , i.e. when the lowest set bit is the only set bit. A positive integer with exactly one set bit is for some . The n > 0 guard matters: too, and in two's complement INT_MIN (1000…0) also has a single set bit but is negative.

JavaScript's 32-bit trap

isPowerOfTwo above is correct for . For larger numbers, & first truncates both operands to 32 bits, so isPowerOfTwo(6442450944) (, not a power of two) returns true. For big values use Number.isInteger(Math.log2(n)) with care about floating point, or BigInt: n > 0n && (n & (n - 1n)) === 0n.

2. Count Set Bits (Popcount)

Brian Kernighan's algorithm: clears the lowest set bit. Count how many times you can do this before reaching zero.

TypeScript:

function countSetBits(n: number): number {
  let count = 0;
  while (n > 0) {
    n &= n - 1; // clear lowest set bit
    count++;
  }
  return count;
}

Python:

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

# Python built-in alternative
bin(42).count('1')  # 3

TIP

Python's bin(n).count('1') is concise but creates a string. For competitive programming, n.bit_count() (Python 3.10+) is both fast and clean.

Negative inputs

Both snippets above assume . The TypeScript loop returns 0 for any negative input (it never enters the loop). The Python loop never terminates for a negative input: a Python int has infinitely many leading 1s, so clearing them one at a time never reaches 0. Mask to a fixed width first — count_set_bits(n & 0xFFFFFFFF) — or use while (n !== 0) in TypeScript, which counts the 32-bit pattern (32 for −1). The section Popcount: four ways to count set bits below covers faster methods and each language's builtin.

3. Swap Without Temporary Variable

XOR swap exploits the self-cancellation property:

TypeScript:

function xorSwap(a: number, b: number): [number, number] {
  a ^= b; // a now holds a XOR b
  b ^= a; // b now holds original a
  a ^= b; // a now holds original b
  return [a, b];
}

Python:

def xor_swap(a: int, b: int) -> tuple[int, int]:
    a ^= b
    b ^= a
    a ^= b
    return a, b

# Python makes this unnecessary: a, b = b, a

WARNING

XOR swap fails when a and b refer to the same memory location (both become 0). In practice, use standard swaps — XOR swap is an interview trick, not production code.

Proof. Call the original values and . After line 1, . After line 2, (the two s cancel). After line 3, . If both names are the same variable, line 1 computes and the original value is lost — that is the aliasing bug in the warning. Compilers already optimise ordinary swaps, so XOR swap is usually also slower (each line waits for the previous one).

4. Get / Set / Clear / Toggle a Specific Bit

TypeScript:

// Get the i-th bit (0-indexed from right)
function getBit(n: number, i: number): number {
  return (n >> i) & 1;
}

// Set the i-th bit to 1
function setBit(n: number, i: number): number {
  return n | (1 << i);
}

// Clear the i-th bit to 0
function clearBit(n: number, i: number): number {
  return n & ~(1 << i);
}

// Toggle the i-th bit
function toggleBit(n: number, i: number): number {
  return n ^ (1 << i);
}

Python:

def get_bit(n: int, i: int) -> int:
    return (n >> i) & 1

def set_bit(n: int, i: int) -> int:
    return n | (1 << i)

def clear_bit(n: int, i: int) -> int:
    return n & ~(1 << i)

def toggle_bit(n: int, i: int) -> int:
    return n ^ (1 << i)

Each works because 1 << i is a mask with only bit set: OR with 1 forces a bit on, AND with 0 forces it off (and ~(1 << i) is 0 only at bit ), XOR with 1 flips it, and everything else is combined with the neutral value (OR 0, AND 1, XOR 0) and left alone. Two useful relatives: set the lowest bits with (1 << k) - 1, and assign bit to a value with (n & ~(1 << i)) | (v << i).

5. Isolate the Lowest Set Bit

This works because in two's complement is , which flips all bits and adds 1.

In detail (see the picture at the top of this section): , so . This is the lowbit function behind Fenwick trees: index is responsible for the elements ending at . Related one-liners: the number of trailing zeros is ctz(n) (__builtin_ctz, Integer.numberOfTrailingZeros, (n & -n).bit_length() - 1 in Python, 31 - Math.clz32(n & -n) in JS), and the highest set bit is 1 << (bit_length(n) - 1).

6. Check if Even or Odd

This one is also a correctness tool, not just a speed trick: in Java, C++ and JavaScript, n % 2 is −1 for negative odd , so the test n % 2 == 1 misses −3. (n & 1) == 1 is right for every two's complement integer. (Speed is a wash: compilers already turn n % 2 == 0 into a bit test.)

7. XOR identities worth memorising

  • Addition = XOR + carries. : XOR adds columns without carrying, AND finds the carries (LeetCode 371).
  • XOR of has period 4. is , , , when is . Proof: for even , the pair , so every aligned block of four XORs to . That gives "missing number" and "XOR of a range" in .
  • Prefix XOR. With , the XOR of is — the same trick as prefix sums, because XOR is its own inverse.
  • Parity masks. Toggle bit per letter ; two prefixes with equal masks bound a substring where every letter appears an even number of times.
  • Hamming distance. The number of positions where and differ is popcount(a ^ b).

Popcount: four ways to count set bits

Popcount (population count, also called Hamming weight) is the number of 1 bits in a word. Modern CPUs have an instruction for it (POPCNT on x86, CNT on ARM).

Methods 1–2 — test every bit ( steps) or Kernighan (x &= x - 1 until zero: one step per set bit). Kernighan on 44:

Stepx (binary)xcount
start101100440
1101000401
2100000322
300000003

Method 3 — lookup table of 256 byte counts: four lookups per 32-bit word, but the table competes for cache.

Method 4 — SWAR ("SIMD Within A Register"): treat the word as many small counters and add them in parallel:

x = x - ((x >> 1) & 0x55555555);                // 16 counters of 2 bits: each holds popcount of its pair
x = (x & 0x33333333) + ((x >> 2) & 0x33333333); // 8 counters of 4 bits
x = (x + (x >> 4)) & 0x0F0F0F0F;                // 4 counters of 8 bits
return (x * 0x01010101) >> 24;                  // sum the 4 bytes into the top byte (32-bit multiply)

Why line 1 works: a pair with value holds ones, and ; (x >> 1) & 0x55… extracts each pair's , and since no borrow crosses pairs. Later lines add neighbouring counters, which cannot overflow (a 4-bit counter holds at most 4). The multiply sums all bytes into the top byte. Trace on the 8-bit value 218 (using the 8-bit masks 0x55, 0x33, 0x0F):

StagePatternRead as counters
input11 01 10 10four pairs
after line 110 01 01 012, 1, 1, 1 ones per pair
after line 20011 00103, 2 ones per nibble
after line 30000 01015 ones in the byte

levels, no branches, no memory (Warren, Hacker's Delight, §5-1).

Builtins — use these in real code:

Language32-bit64-bitNotes
Pythonx.bit_count() (3.10+)same — ints are unboundedbin(x).count("1") on older versions; both count the magnitude for negatives
JavaInteger.bitCount(x)Long.bitCount(x)JIT intrinsic → POPCNT on x86
C++__builtin_popcount(x) (GCC/Clang), std::popcount(x) (C++20, unsigned types only)__builtin_popcountll, std::popcount(uint64_t)std::bitset<N>::count(); compile with -mpopcnt or -march=native to get the instruction
JavaScriptnone — use SWAR with >>> and Math.imulBigInt loop, or split into two 32-bit halvesMath.clz32 exists for leading zeros

Single Number (XOR Trick)

Problem: Given an array where every element appears twice except one, find that single element.

Since and , XORing all elements cancels out duplicates:

TypeScript:

function singleNumber(nums: number[]): number {
  return nums.reduce((xor, num) => xor ^ num, 0);
}

// Example: [4, 1, 2, 1, 2] → 4^1^2^1^2 = 4

Python:

from functools import reduce
from operator import xor

def single_number(nums: list[int]) -> int:
    return reduce(xor, nums)

# Or simply:
def single_number_loop(nums: list[int]) -> int:
    result = 0
    for num in nums:
        result ^= num
    return result
MetricValue
Time — single pass
Space — no extra storage

Proof. XOR is commutative and associative, so we may reorder the input to put each pair side by side without changing the result. Each pair XORs to 0, and . The same argument shows something stronger: XOR of a multiset equals the XOR of the values that occur an odd number of times. Missing Number (LeetCode 268) is the same trick — XOR all indices together with all values, and the missing index is the only number that appears once.

Single Number II: everything appears three times except one

Problem: every value appears exactly three times, except one value that appears once. Find it in time and space. XOR no longer works: three copies XOR to the value itself, not zero.

Idea 1 — count each bit mod 3. At one bit position, each tripled value contributes 0 or 3 ones and the single value 0 or 1, so the count mod 3 is the single value's bit. time. In Python, turn bit 31 back into a sign at the end.

Idea 2 — a mod-3 counter in two words. Idea 1 runs 32 counters. A mod-3 counter needs two bits, so store all 32 low bits in ones and all high bits in twos. Per position, the state walks on each 1:

graph LR
    S0["count 0 (ones=0, twos=0)"] -->|"see a 1"| S1["count 1 (ones=1, twos=0)"]
    S1 -->|"see a 1"| S2["count 2 (ones=0, twos=1)"]
    S2 -->|"see a 1"| S0

Seeing a 0 leaves the state alone. Two lines implement this transition for all 32 positions at once:

ones = (ones ^ x) & ~twos
twos = (twos ^ x) & ~ones      # uses the NEW ones

Check one bit position when 's bit is 1: → ones , twos → ✓; → ✓; → ✓. When the bit is 0, nothing changes (state is unreachable, so the masks clear nothing). At the end each position's count is the single value's bit, held in ones.

Trace on [2, 2, 3, 2] (answer 3):

Read xx binaryones aftertwos afterWhat happened
——00 (0)00 (0)start
21010 (2)00 (0)bit 1 seen once
21000 (0)10 (2)bit 1 seen twice
31101 (1)00 (0)bit 1 third time → reset; bit 0 once
21011 (3)00 (0)bit 1 once again

Answer: ones = 3 ✓. Four-language code is in Implementation. The recipe — design a tiny automaton per bit, run all bits in parallel — handles " times except one" with counter words.

Two Single Numbers

Problem: Every element appears twice except two elements. Find both.

Strategy: XOR all elements to get . Find any set bit in the result (it distinguishes from ). Partition elements by that bit and XOR each group separately.

TypeScript:

function twoSingleNumbers(nums: number[]): [number, number] {
  // XOR of all gives xorAll = x ^ y
  let xorAll = 0;
  for (const num of nums) xorAll ^= num;

  // Find rightmost set bit (where x and y differ)
  const diffBit = xorAll & -xorAll;

  let x = 0, y = 0;
  for (const num of nums) {
    if (num & diffBit) {
      x ^= num;
    } else {
      y ^= num;
    }
  }

  return [x, y];
}

Python:

def two_single_numbers(nums: list[int]) -> tuple[int, int]:
    xor_all = 0
    for num in nums:
        xor_all ^= num

    diff_bit = xor_all & -xor_all

    x, y = 0, 0
    for num in nums:
        if num & diff_bit:
            x ^= num
        else:
            y ^= num

    return x, y

Proof. Since , and has at least one set bit; diffBit is its lowest. At that position and differ, so they land in different groups. Every duplicated value has the same bit in both copies, so both copies land in the same group and cancel there. Each group therefore XORs to exactly one of the singles. Trace on [1, 2, 1, 3, 2, 5]: the XOR of everything is (110), diffBit (010); the group with bit 1 set is → 3, the other is → 5.

`-xorAll` can overflow

If happens to be INT_MIN (only the sign bit set), -xorAll overflows. Java wraps it back to INT_MIN, which is still the right mask. In C++ it is undefined behaviour on int — compute on unsigned (u & (0u - u)) instead. Python has no overflow; JavaScript's - produces as a float and & converts it back to INT_MIN, which also happens to work.

Reverse Bits

Problem: reverse the order of the 32 bits of an unsigned integer. Bit 0 becomes bit 31, bit 1 becomes bit 30, and so on. Example: 00000010100101000001111010011100 (43261596) becomes 00111001011110000010100101000000 (964176192).

Loop version. Pop bits off the input's bottom and push them onto the result's bottom, 32 times:

r = 0
repeat 32 times:
    r = (r << 1) | (x & 1)
    x = x >> 1            # logical shift: >>> in Java/JS

After 32 steps bit sits at . Loop exactly 32 times, not "while x != 0": the input's leading zeros must still be shifted in.

Divide-and-conquer version. Swap halves, then bytes, nibbles, pairs and single bits — five mask-and-shift steps:

x = (x >> 16) | (x << 16);
x = ((x & 0xFF00FF00) >> 8) | ((x & 0x00FF00FF) << 8);
x = ((x & 0xF0F0F0F0) >> 4) | ((x & 0x0F0F0F0F) << 4);
x = ((x & 0xCCCCCCCC) >> 2) | ((x & 0x33333333) << 2);
x = ((x & 0xAAAAAAAA) >> 1) | ((x & 0x55555555) << 1);

Java has Integer.reverse(x) (a result with bit 31 set prints as negative); in JavaScript finish with >>> 0; Clang has __builtin_bitreverse32; ARM has an RBIT instruction.

Counting Bits with DP

Problem (LeetCode 338): ans[i] = popcount(i) for every in , in . i >> 1 is without its last bit, and that bit is i & 1, so

i >> 1 < i is already filled. (Equally good: .)

binaryans
00000——0
10001011
20010101
30011112
40100201
50101212
60110302
70111313
81000401

This is the smallest DP over bit structure; Bitmask DP and SOS DP scale it up.

Bitmask DP

Bitmasks represent subsets of a set using binary numbers. If you have elements, a bitmask of bits can represent any subset. Bit is 1 if element is in the subset.

This section covers the enumeration toolkit — every way of walking over masks that a bitmask algorithm needs. The full dynamic-programming technique (state design, TSP, assignment, Hamiltonian paths, profile DP) gets its own lesson, Bitmask DP, and the "sum over all submasks for every mask in " technique is SOS DP.

Subset Iteration

TypeScript:

function allSubsets(n: number): number[][] {
  const subsets: number[][] = [];

  for (let mask = 0; mask < (1 << n); mask++) {
    const subset: number[] = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        subset.push(i);
      }
    }
    subsets.push(subset);
  }

  return subsets;
}

Python:

def all_subsets(n: int) -> list[list[int]]:
    subsets = []
    for mask in range(1 << n):
        subset = [i for i in range(n) if mask & (1 << i)]
        subsets.append(subset)
    return subsets

Counting visits every subset exactly once, because each -bit integer is a unique subset ( to list elements). And every proper submask is numerically smaller than its mask, so a DP that reads only submasks can loop mask upwards.

Enumerating all submasks of a mask

A submask of has ; 1011 has of them. Instead of testing all masks, the standard loop visits only submasks:

for (int s = m; s > 0; s = (s - 1) & m) {
    // use s  (every non-empty submask of m, in decreasing order)
}
// then handle s = 0 separately if you need the empty set

Why (s - 1) & m is the next submask. Claim: for a non-empty submask of , the value (s - 1) & m is the largest submask of smaller than . Write (lowest set bit at position ). Then . Any submask must agree with on the bits above the first position where they differ, and at that position has 0 where has 1; the largest such differs as low as possible — at position , the lowest 1 of — and then takes every bit of below . That is exactly : it keeps (already inside ), clears bit , and keeps the bits of below . So the loop walks the submasks in strictly decreasing order without skipping any, and stops after reaches 0.

Trace for (1011):

Stepsbinarys - 1(s - 1) & m
111101110101010 = 10
210101010011001 = 9
39100110001000 = 8
48100001110011 = 3
53001100100010 = 2
62001000010001 = 1
71000100000000 = 0 → stop

Eight submasks, including 0 after the loop. At step 4, s - 1 = 0111 has bit 2, which is not in ; the AND drops it and jumps to 3 — that jump is the saving.

A common variant

If you need the empty submask inside the loop, use for (s = m; ; s = (s - 1) & m) { use(s); if (s == 0) break; }. Writing s >= 0 as the condition is a bug: (0 - 1) & m is again, so the loop never ends.

Why "all submasks of all masks" costs , not

Many bitmask DPs do this:

for (int m = 0; m < (1 << n); m++)
    for (int s = m; s > 0; s = (s - 1) & m)
        dp[m] = combine(dp[m], dp[s], dp[m ^ s]);

A naive bound says masks × up to submasks . The true total is . Two proofs:

Counting proof. Each pair with corresponds to assigning each of the elements one of three labels: "not in ", "in but not in ", "in " (which implies in ). Different pairs give different labelings and every labeling gives a pair, so there are exactly pairs.

Algebra proof. A mask with set bits has submasks, and there are masks with set bits. By the binomial theorem:

For : versus — 315× less. (The Implementation programs confirm by brute force.) If the combine step is a sum over submasks, SOS DP does it in .

Iterating over supersets

The mirror image: all masks with , where is the universe. Increment and force 's bits back on:

for (int s = m; s < (1 << n); s = (s + 1) | m) {
    // use s  (every superset of m, increasing)
}

Why it works. Think of as plus some free bits (bits outside ). Adding 1 to turns its trailing 1s into 0s and the lowest 0 into a 1. All of 's bits are 1 in , so the lowest 0 is always a free bit, and on the free bits alone this is exactly "add 1 to , skipping over 's positions". The carry did clear some of 's bits on the way; | m puts them back. So (s + 1) | m is the smallest superset of larger than , the loop visits every superset in increasing order, and it stops when the free bits overflow past bit . Trace for (0101), : 5 (0101) → 6 | 5 = 7 (0111) → 8 | 5 = 13 (1101) → 14 | 5 = 15 (1111) → 16 | 5 = 21 ≥ 16, stop. Four supersets ✓.

Both this and "submasks of the complement, OR " take .

Gosper's hack: the next subset with exactly elements

To visit only the subsets of size exactly ("choose 3 of 20 servers": masks instead of ), Gosper's hack (Bill Gosper, HAKMEM item 175, 1972) takes a mask and returns the next larger integer with the same number of set bits:

unsigned next_combination(unsigned x) {   // x != 0
    unsigned c = x & -x;          // lowest set bit
    unsigned r = x + c;           // add it: the lowest block of 1s collapses into one carry bit
    return (((r ^ x) >> 2) / c) | r;   // re-insert the leftover 1s at the very bottom
}

Derivation. Write : the lowest block of ones starts at position . To grow as little as possible with the same popcount, move the block's top one up into the 0 above it, and push the other ones down to positions :

Now follow the code:

  • c = x & -x , the lowest set bit.
  • r = x + c : adding to a block of ones at position carries all the way through it, giving the "moved top one" and zeros below.
  • r ^ x marks the bits that changed: the ones of the block plus the new bit above it, i.e. ones starting at position , value .
  • >> 2 then / c shifts that right by in total (dividing by is a right shift by ; floor division drops the bits that fall off), leaving ones at the bottom.
  • | r combines: plus ones at the bottom. ✓

To list all -subsets of elements, start from (the smallest -bit mask) and stop once . Trace for , :

Stepxbinarycrnext
17001111811
2110101111213
3130110111414
4140111021619
5191001112021
6211010112222
7221011022425
8251100112626
9261101022828
10281110043235 ≥ 32 → stop

Ten masks ✓, in increasing order. Edge cases: handle separately (/ c would divide by zero), and leave room for r to reach — with signed 32-bit ints. Replacing / c with >> ctz(x) avoids the division.

Traveling Salesman with Bitmask DP

The classic bitmask DP problem. Visit all cities exactly once with minimum cost. State: (current_city, visited_set).

TypeScript:

function tsp(dist: number[][]): number {
  const n = dist.length;
  const ALL = (1 << n) - 1;
  const INF = Infinity;

  // dp[mask][i] = min cost to visit cities in mask, ending at i
  const dp: number[][] = Array.from(
    { length: 1 << n },
    () => new Array(n).fill(INF)
  );

  dp[1][0] = 0; // start at city 0

  for (let mask = 1; mask <= ALL; mask++) {
    for (let u = 0; u < n; u++) {
      if (dp[mask][u] === INF) continue;
      if (!(mask & (1 << u))) continue;

      for (let v = 0; v < n; v++) {
        if (mask & (1 << v)) continue; // already visited
        const nextMask = mask | (1 << v);
        dp[nextMask][v] = Math.min(
          dp[nextMask][v],
          dp[mask][u] + dist[u][v]
        );
      }
    }
  }

  // Return to start
  let result = INF;
  for (let u = 1; u < n; u++) {
    result = Math.min(result, dp[ALL][u] + dist[u][0]);
  }

  return result;
}

Python:

def tsp(dist: list[list[int]]) -> int:
    n = len(dist)
    ALL = (1 << n) - 1
    INF = float('inf')

    # dp[mask][i] = min cost visiting cities in mask, ending at i
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # start at city 0

    for mask in range(1, ALL + 1):
        for u in range(n):
            if dp[mask][u] == INF:
                continue
            if not (mask & (1 << u)):
                continue

            for v in range(n):
                if mask & (1 << v):
                    continue
                next_mask = mask | (1 << v)
                dp[next_mask][v] = min(
                    dp[next_mask][v],
                    dp[mask][u] + dist[u][v]
                )

    return min(dp[ALL][u] + dist[u][0] for u in range(1, n))

Complexity: time, space. Feasible for .

WARNING

Bitmask DP is exponential by nature. It is only practical for small (typically ). For larger problems, use approximation algorithms or heuristics.

This is the Held–Karp algorithm (Bellman 1962; Held and Karp 1962). The forward loop is valid because nextMask > mask. For the final min is empty (Python raises ValueError); a one-city tour costs 0. Reconstruction and variants are in Bitmask DP.

Gray Code

A Gray code is an ordering of all bit patterns of length in which consecutive patterns differ in exactly one bit. Frank Gray of Bell Labs patented the "reflected binary code" in 1953 (filed 1947). The standard one has a closed form:

binary bit that changed from previous
0000000000—
1001000001bit 0
2010001011bit 1
3011001010bit 0
4100010110bit 2
5101010111bit 0
6110011101bit 1
7111011100bit 0

The last code 100 and the first 000 also differ in one bit, so the sequence is a cycle through every corner of an -dimensional cube.

graph LR
    A["000"] --> B["001"] --> C["011"] --> D["010"] --> E["110"] --> F["111"] --> G["101"] --> H["100"]
    H -->|"wraps around"| A

Proof that neighbours differ in exactly one bit. First, is linear over XOR: , because shifting distributes over XOR. Now take and . Write with trailing ones; then , so (a block of ones). Then

a single bit — bit , the number of trailing ones of (the same rule that picks which disk moves in the Towers of Hanoi). The wrap-around: , one bit.

The inverse. Given a Gray code , recover . Since for each bit , the top bit of equals the top bit of , and each lower bit is . Unrolling: is the XOR of all right-shifts of :

Example: (110) → , and ✓. For 32 bits, five steps suffice: g ^= g >> 16; g ^= g >> 8; g ^= g >> 4; g ^= g >> 2; g ^= g >> 1.

"Reflected" refers to the recursive construction: the -bit list is the -bit list with a 0 in front, then the same list reversed with a 1 in front, so the seam changes only the new top bit.

Uses. Position encoders (a reading taken mid-change is off by at most one step; in plain binary, 7 → 8 flips four bits and a half-read could give 15); Karnaugh maps; FIFO pointers that cross clock domains in chip design; Gray-labelled QAM constellations in digital radio, so the likeliest symbol error costs one bit.

Maximum XOR of Two Numbers

Problem (LeetCode 421): maximise a[i] ^ a[j]. Brute force is .

Key insight: higher bits dominate, since (all lower bits together). So decide the answer bit by bit from the top, greedily trying to make each bit 1. With a hash set: for bit from high to low, let want = ans | (1 << b); if two prefixes x >> b XOR to want >> b (check in the set), keep want. total. The trie version inserts each number's bits top-down and walks toward the opposite bit wherever possible; it also supports online inserts and deletes. Full proof and code: The XOR trie.

Example: [3, 10, 5, 25, 2, 8] → 28 . Maximum XOR of a subarray: the same trie over prefix XORs. Of a subset: a linear basis (Gaussian elimination over GF(2)).

Bitsets and bit-parallel tricks

A bitset is an array of machine words used as one long array of bits. AND, OR, XOR and shifts process 64 bits per instruction, so an inner loop of boolean updates often gets 64× faster — the same Big-O divided by the word size , written . C++ has std::bitset<N> (fixed size, with shifts and count()); Java has java.util.BitSet (and, or, cardinality, nextSetBit, but no shifts); in Python a plain int is a bitset whose operations run in C; JavaScript has Uint32Array or BigInt.

Example — subset sum. "Which totals can a subset of these weights reach?" Adding weight to the DP reach[t] |= reach[t - w] is a single shifted OR:

reach = 1                  # bit t set  <=>  sum t is reachable; only 0 at first
for w in [3, 5, 7]:
    reach |= reach << w
# reachable sums: [0, 3, 5, 7, 8, 10, 12, 15]

Time drops from to : for , , about word operations instead of boolean ones.

Other bit-parallel classics: Shift-And string matching (Baeza-Yates and Gonnet, 1992) keeps a word whose bit means "the last characters match the pattern's first ", updated per character by D = ((D << 1) | 1) & mask[c] — the automaton view of KMP, used by agrep; Myers' bit-vector edit distance (JACM 1999); transitive closure with bitset rows (); common-neighbour counts as popcount(adj[u] & adj[v]); and the chess bitboards below.

The ladder: brute force → better → optimal

Two ladders you are likely to be asked to climb.

Ladder A: count the set bits of every number from 0 to

RungMethodTimeWhy it is better than the rung above
1Convert each number to a string, count '1' characters plus string allocation—
2Bit loop per number, (x >> i) & 1 for all bitsNo strings; but still touches every zero bit
3Kernighan per numberSkips zero bits; average popcount is about
4Builtin / SWAR per number with per callConstant work per number, but still recomputes shared structure
5DP: ans[i] = ans[i >> 1] + (i & 1), one add per numberReuses the answer for ; no popcount at all

Ladder B: for every mask, combine over all of its submasks

RungMethodTime ()Why it is better
1For each , for each in , test s & m == s—
2Submask loop s = (s - 1) & mVisits only real submasks; the proof above
3SOS DP (if the combine step is a sum/OR/min over submasks)Shares partial sums across masks, one dimension at a time

Rung 2 is the intended solution when the combine step does not decompose (e.g. "split into and , take the best"); rung 3 is SOS DP.

Correctness

The proofs sit next to each technique; these are the reusable tools behind them.

  1. The lowest-set-bit picture , , — behind power-of-two, Kernighan, Fenwick, Gosper and Single Number III.
  2. Bit independence. AND, OR, XOR and NOT act on each position separately, so a one-bit truth-table check proves a whole-word identity (Single Number II's automaton).
  3. XOR is a group where every element is its own inverse — reordering is free and pairs cancel.
  4. "Next element" arguments for loops. Show each step jumps to the next member of the target set in a fixed order (largest smaller submask, smallest larger superset, smallest larger same-popcount integer). Strict monotonicity also proves termination.
  5. Counting by labels () or binomial sums for cost.
  6. Exhaustive testing at small widths. The Implementation programs compare every clever loop with brute force on all masks up to 8–10 bits; do the same for any trick you invent.

Complexity

OperationTimeExtra space
AND, OR, XOR, NOT, shift, one instruction
Popcount hardware; SWAR; Kernighan
Single Number I / II / III ( for the bit-count version of II)
Counting bits output only
All subsets / their elements /
Submasks of / of all masks /
Supersets of
-subsets via Gosper
Gray code / inverse /
Maximum XOR pair for -bit values set or trie
Bitset op on bits, words

Implementation

Two groups of complete programs. The first enumerates masks (submasks, supersets, Gosper's hack) and checks the total; the second has Gray code with its inverse and Single Number II both ways. Every program asserts the worked examples from this lesson and cross-checks against brute force on all small inputs.

Enumeration: submasks, supersets, Gosper's hack

from itertools import combinations
from math import comb


def submasks(m: int) -> list[int]:
    """Every submask of m, largest first, ending with 0."""
    out = []
    s = m
    while s:                      # the loop stops before 0 ...
        out.append(s)
        s = (s - 1) & m           # largest submask of m smaller than s
    out.append(0)                 # ... so add the empty submask here
    return out


def supersets(m: int, n: int) -> list[int]:
    """Every superset of m inside the n-bit universe, smallest first."""
    out = []
    s = m
    while s < (1 << n):
        out.append(s)
        s = (s + 1) | m           # smallest superset of m larger than s
    return out


def next_combination(x: int) -> int:
    """Gosper's hack: next larger integer with the same number of set bits (x > 0)."""
    c = x & -x                    # lowest set bit
    r = x + c                     # lowest block of 1s collapses into one carry bit
    return (((r ^ x) >> 2) // c) | r   # leftover 1s go back to the bottom


def k_subsets(n: int, k: int) -> list[int]:
    """All n-bit masks with exactly k bits set, in increasing order."""
    if k == 0:
        return [0]
    out = []
    x = (1 << k) - 1
    while x < (1 << n):
        out.append(x)
        x = next_combination(x)
    return out


def main() -> None:
    assert submasks(0b1011) == [11, 10, 9, 8, 3, 2, 1, 0]
    assert supersets(0b0101, 4) == [5, 7, 13, 15]
    assert k_subsets(5, 3) == [7, 11, 13, 14, 19, 21, 22, 25, 26, 28]

    # "for every mask, for every submask" does 3^n steps in total
    for n in range(1, 11):
        assert sum(len(submasks(m)) for m in range(1 << n)) == 3 ** n

    # cross-check every function against brute force
    for n in range(1, 9):
        for m in range(1 << n):
            assert submasks(m) == sorted((s for s in range(1 << n) if s & m == s), reverse=True)
            assert supersets(m, n) == [s for s in range(1 << n) if s & m == m]
        for k in range(n + 1):
            brute = sorted(sum(1 << i for i in c) for c in combinations(range(n), k))
            assert k_subsets(n, k) == brute and len(brute) == comb(n, k)

    print("submasks(11):", submasks(11))
    print("k_subsets(5, 3):", k_subsets(5, 3))
    print("all enumeration tests passed")


if __name__ == "__main__":
    main()
import java.util.ArrayList;
import java.util.List;

public class Main {
    // Every submask of m, largest first, ending with 0.
    static List<Integer> submasks(int m) {
        List<Integer> out = new ArrayList<>();
        for (int s = m; s != 0; s = (s - 1) & m) out.add(s);
        out.add(0);
        return out;
    }

    // Every superset of m inside the n-bit universe (n <= 30), smallest first.
    static List<Integer> supersets(int m, int n) {
        List<Integer> out = new ArrayList<>();
        for (int s = m; s < (1 << n); s = (s + 1) | m) out.add(s);
        return out;
    }

    // Gosper's hack: next larger int with the same number of set bits (x > 0).
    static int nextCombination(int x) {
        int c = x & -x;                       // lowest set bit
        int r = x + c;                        // collapse the lowest block of 1s
        return (((r ^ x) >>> 2) / c) | r;     // re-insert the leftover 1s at the bottom
    }

    // All n-bit masks with exactly k bits set (n <= 30), increasing.
    static List<Integer> kSubsets(int n, int k) {
        List<Integer> out = new ArrayList<>();
        if (k == 0) { out.add(0); return out; }
        for (int x = (1 << k) - 1; x < (1 << n); x = nextCombination(x)) out.add(x);
        return out;
    }

    static long binom(int n, int k) {
        long r = 1;
        for (int i = 1; i <= k; i++) r = r * (n - k + i) / i;
        return r;
    }

    static void check(boolean ok, String what) {
        if (!ok) throw new AssertionError(what);
    }

    public static void main(String[] args) {
        check(submasks(0b1011).equals(List.of(11, 10, 9, 8, 3, 2, 1, 0)), "submasks");
        check(supersets(0b0101, 4).equals(List.of(5, 7, 13, 15)), "supersets");
        check(kSubsets(5, 3).equals(List.of(7, 11, 13, 14, 19, 21, 22, 25, 26, 28)), "gosper");

        long pow3 = 1;
        for (int n = 1; n <= 10; n++) {
            pow3 *= 3;
            long total = 0;
            for (int m = 0; m < (1 << n); m++) total += submasks(m).size();
            check(total == pow3, "3^n total");
        }

        for (int n = 1; n <= 8; n++) {
            for (int m = 0; m < (1 << n); m++) {
                List<Integer> sub = new ArrayList<>(), sup = new ArrayList<>();
                for (int s = (1 << n) - 1; s >= 0; s--) if ((s & m) == s) sub.add(s);
                for (int s = 0; s < (1 << n); s++) if ((s & m) == m) sup.add(s);
                check(submasks(m).equals(sub), "submask brute");
                check(supersets(m, n).equals(sup), "superset brute");
            }
            for (int k = 0; k <= n; k++) {
                List<Integer> brute = new ArrayList<>();
                for (int x = 0; x < (1 << n); x++) if (Integer.bitCount(x) == k) brute.add(x);
                check(kSubsets(n, k).equals(brute) && brute.size() == binom(n, k), "gosper brute");
            }
        }

        System.out.println("submasks(11): " + submasks(11));
        System.out.println("kSubsets(5, 3): " + kSubsets(5, 3));
        System.out.println("all enumeration tests passed");
    }
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

// Unsigned types throughout: wrap-around is defined, shifts of the top bit are safe.

vector<uint32_t> submasks(uint32_t m) {  // largest first, ending with 0
    vector<uint32_t> out;
    for (uint32_t s = m; s != 0; s = (s - 1) & m) out.push_back(s);
    out.push_back(0);
    return out;
}

vector<uint32_t> supersets(uint32_t m, int n) {  // n <= 31, smallest first
    vector<uint32_t> out;
    for (uint32_t s = m; s < (1u << n); s = (s + 1) | m) out.push_back(s);
    return out;
}

uint32_t nextCombination(uint32_t x) {  // Gosper's hack, x != 0
    uint32_t c = x & -x;                // lowest set bit (unary minus on unsigned is modular)
    uint32_t r = x + c;                 // collapse the lowest block of 1s
    return (((r ^ x) >> 2) / c) | r;    // re-insert the leftover 1s at the bottom
}

vector<uint32_t> kSubsets(int n, int k) {  // n <= 30
    if (k == 0) return {0};
    vector<uint32_t> out;
    for (uint32_t x = (1u << k) - 1; x < (1u << n); x = nextCombination(x)) out.push_back(x);
    return out;
}

void print(const char* label, const vector<uint32_t>& v) {
    cout << label;
    for (uint32_t x : v) cout << ' ' << x;
    cout << '\n';
}

int main() {
    assert((submasks(0b1011) == vector<uint32_t>{11, 10, 9, 8, 3, 2, 1, 0}));
    assert((supersets(0b0101, 4) == vector<uint32_t>{5, 7, 13, 15}));
    assert((kSubsets(5, 3) == vector<uint32_t>{7, 11, 13, 14, 19, 21, 22, 25, 26, 28}));

    uint64_t pow3 = 1;
    for (int n = 1; n <= 10; n++) {
        pow3 *= 3;
        uint64_t total = 0;
        for (uint32_t m = 0; m < (1u << n); m++) total += submasks(m).size();
        assert(total == pow3);
    }

    for (int n = 1; n <= 8; n++) {
        for (uint32_t m = 0; m < (1u << n); m++) {
            vector<uint32_t> sub, sup;
            for (int s = (1 << n) - 1; s >= 0; s--)
                if ((uint32_t(s) & m) == uint32_t(s)) sub.push_back(s);
            for (uint32_t s = 0; s < (1u << n); s++)
                if ((s & m) == m) sup.push_back(s);
            assert(submasks(m) == sub);
            assert(supersets(m, n) == sup);
        }
        for (int k = 0; k <= n; k++) {
            vector<uint32_t> brute;
            for (uint32_t x = 0; x < (1u << n); x++)
                if (__builtin_popcount(x) == k) brute.push_back(x);
            assert(kSubsets(n, k) == brute);
        }
    }

    print("submasks(11):", submasks(11));
    print("kSubsets(5, 3):", kSubsets(5, 3));
    cout << "all enumeration tests passed\n";
}
// JS bitwise operators work on 32-bit signed ints, so keep n <= 30.

function submasks(m: number): number[] {
  const out: number[] = [];
  for (let s = m; s !== 0; s = (s - 1) & m) out.push(s); // largest submask below s
  out.push(0);
  return out;
}

function supersets(m: number, n: number): number[] {
  const out: number[] = [];
  for (let s = m; s < 1 << n; s = (s + 1) | m) out.push(s); // smallest superset above s
  return out;
}

function nextCombination(x: number): number {
  const c = x & -x; // lowest set bit
  const r = x + c; // collapse the lowest block of 1s
  return Math.floor(((r ^ x) >>> 2) / c) | r; // integer division: Math.floor is required
}

function kSubsets(n: number, k: number): number[] {
  if (k === 0) return [0];
  const out: number[] = [];
  for (let x = (1 << k) - 1; x < 1 << n; x = nextCombination(x)) out.push(x);
  return out;
}

function popcount(x: number): number {
  let c = 0;
  for (; x !== 0; x &= x - 1) c++;
  return c;
}

function check(ok: boolean, what: string): void {
  if (!ok) throw new Error("check failed: " + what);
}

const same = (a: number[], b: number[]): boolean =>
  a.length === b.length && a.every((v, i) => v === b[i]);

check(same(submasks(0b1011), [11, 10, 9, 8, 3, 2, 1, 0]), "submasks");
check(same(supersets(0b0101, 4), [5, 7, 13, 15]), "supersets");
check(same(kSubsets(5, 3), [7, 11, 13, 14, 19, 21, 22, 25, 26, 28]), "gosper");

for (let n = 1; n <= 10; n++) {
  let total = 0;
  for (let m = 0; m < 1 << n; m++) total += submasks(m).length;
  check(total === 3 ** n, "3^n total");
}

for (let n = 1; n <= 8; n++) {
  for (let m = 0; m < 1 << n; m++) {
    const sub: number[] = [];
    const sup: number[] = [];
    for (let s = (1 << n) - 1; s >= 0; s--) if ((s & m) === s) sub.push(s);
    for (let s = 0; s < 1 << n; s++) if ((s & m) === m) sup.push(s);
    check(same(submasks(m), sub), "submask brute");
    check(same(supersets(m, n), sup), "superset brute");
  }
  for (let k = 0; k <= n; k++) {
    const brute: number[] = [];
    for (let x = 0; x < 1 << n; x++) if (popcount(x) === k) brute.push(x);
    check(same(kSubsets(n, k), brute), "gosper brute");
  }
}

console.log("submasks(11):", submasks(11).join(" "));
console.log("kSubsets(5, 3):", kSubsets(5, 3).join(" "));
console.log("all enumeration tests passed");

Gray code and Single Number II

import random


def gray(i: int) -> int:
    return i ^ (i >> 1)


def gray_inverse(g: int) -> int:
    i = 0
    while g:                       # i = g ^ (g >> 1) ^ (g >> 2) ^ ...
        i ^= g
        g >>= 1
    return i


def single_number_ii_bits(nums: list[int]) -> int:
    """Every value appears 3 times except one: count each of 32 bits mod 3."""
    result = 0
    for b in range(32):
        if sum((x >> b) & 1 for x in nums) % 3:
            result |= 1 << b
    if result >= 1 << 31:          # bit 31 is the sign bit of a 32-bit int
        result -= 1 << 32
    return result


def single_number_ii(nums: list[int]) -> int:
    """Same problem with a mod-3 counter per bit stored in two words."""
    ones = twos = 0
    for x in nums:
        ones = (ones ^ x) & ~twos
        twos = (twos ^ x) & ~ones
    return ones


def main() -> None:
    assert [gray(i) for i in range(8)] == [0, 1, 3, 2, 6, 7, 5, 4]
    assert gray_inverse(6) == 4 and gray_inverse(11) == 13
    for bits in range(1, 11):
        seq = [gray(i) for i in range(1 << bits)]
        assert sorted(seq) == list(range(1 << bits))           # every pattern exactly once
        for i in range(len(seq)):                               # neighbours (and the wrap) differ in 1 bit
            assert (seq[i] ^ seq[(i + 1) % len(seq)]).bit_count() == 1
            assert gray_inverse(seq[i]) == i

    assert single_number_ii([2, 2, 3, 2]) == 3 == single_number_ii_bits([2, 2, 3, 2])
    assert single_number_ii([-4, 1, 1, 1]) == -4 == single_number_ii_bits([-4, 1, 1, 1])
    rng = random.Random(7)
    for _ in range(300):
        vals = rng.sample(range(-2**31, 2**31), 6)
        nums = [v for v in vals[1:] for _ in range(3)] + [vals[0]]
        rng.shuffle(nums)
        assert single_number_ii(nums) == vals[0] == single_number_ii_bits(nums)

    print("gray(0..7):", [gray(i) for i in range(8)])
    print("all Gray code and Single Number II tests passed")


if __name__ == "__main__":
    main()
import java.util.Arrays;
import java.util.Random;

public class Main {
    static int gray(int i) { return i ^ (i >>> 1); }

    static int grayInverse(int g) {
        int i = 0;
        for (; g != 0; g >>>= 1) i ^= g;   // >>> so negative codes terminate too
        return i;
    }

    static int singleNumberIIBits(int[] nums) {
        int result = 0;
        for (int b = 0; b < 32; b++) {
            int count = 0;
            for (int x : nums) count += (x >>> b) & 1;
            if (count % 3 != 0) result |= 1 << b;   // bit 31 lands on the sign bit: negatives work
        }
        return result;
    }

    static int singleNumberII(int[] nums) {
        int ones = 0, twos = 0;
        for (int x : nums) {
            ones = (ones ^ x) & ~twos;
            twos = (twos ^ x) & ~ones;
        }
        return ones;
    }

    static void check(boolean ok, String what) {
        if (!ok) throw new AssertionError(what);
    }

    public static void main(String[] args) {
        int[] first8 = new int[8];
        for (int i = 0; i < 8; i++) first8[i] = gray(i);
        check(Arrays.equals(first8, new int[] {0, 1, 3, 2, 6, 7, 5, 4}), "gray table");
        check(grayInverse(6) == 4 && grayInverse(11) == 13, "gray inverse");
        for (int bits = 1; bits <= 10; bits++) {
            int size = 1 << bits;
            boolean[] seen = new boolean[size];
            for (int i = 0; i < size; i++) {
                seen[gray(i)] = true;
                check(Integer.bitCount(gray(i) ^ gray((i + 1) % size)) == 1, "one-bit step");
                check(grayInverse(gray(i)) == i, "inverse");
            }
            for (boolean s : seen) check(s, "every pattern");
        }

        check(singleNumberII(new int[] {2, 2, 3, 2}) == 3, "II example");
        check(singleNumberIIBits(new int[] {2, 2, 3, 2}) == 3, "II bits example");
        check(singleNumberII(new int[] {-4, 1, 1, 1}) == -4, "II negative");
        check(singleNumberIIBits(new int[] {-4, 1, 1, 1}) == -4, "II bits negative");
        Random rng = new Random(7);
        for (int t = 0; t < 300; t++) {
            int single = rng.nextInt();
            int[] nums = new int[16];
            for (int j = 0; j < 5; j++) {
                int v = rng.nextInt();
                if (v == single) v ^= 1;
                nums[3 * j] = nums[3 * j + 1] = nums[3 * j + 2] = v;
            }
            nums[15] = single;
            check(singleNumberII(nums) == single && singleNumberIIBits(nums) == single, "II random");
        }

        System.out.println("gray(0..7): " + Arrays.toString(first8));
        System.out.println("all Gray code and Single Number II tests passed");
    }
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>
using namespace std;

uint32_t gray(uint32_t i) { return i ^ (i >> 1); }

uint32_t grayInverse(uint32_t g) {
    uint32_t i = 0;
    for (; g != 0; g >>= 1) i ^= g;
    return i;
}

int32_t singleNumberIIBits(const vector<int32_t>& nums) {
    uint32_t result = 0;
    for (int b = 0; b < 32; b++) {
        int count = 0;
        for (int32_t x : nums) count += (uint32_t(x) >> b) & 1u;
        if (count % 3 != 0) result |= 1u << b;
    }
    return int32_t(result);  // two's complement conversion: guaranteed since C++20, what GCC/Clang always do
}

int32_t singleNumberII(const vector<int32_t>& nums) {
    uint32_t ones = 0, twos = 0;  // unsigned: bitwise ops on the raw pattern
    for (int32_t v : nums) {
        uint32_t x = uint32_t(v);
        ones = (ones ^ x) & ~twos;
        twos = (twos ^ x) & ~ones;
    }
    return int32_t(ones);
}

int main() {
    vector<uint32_t> first8;
    for (uint32_t i = 0; i < 8; i++) first8.push_back(gray(i));
    assert((first8 == vector<uint32_t>{0, 1, 3, 2, 6, 7, 5, 4}));
    assert(grayInverse(6) == 4 && grayInverse(11) == 13);
    for (int bits = 1; bits <= 10; bits++) {
        uint32_t size = 1u << bits;
        vector<bool> seen(size, false);
        for (uint32_t i = 0; i < size; i++) {
            seen[gray(i)] = true;
            assert(__builtin_popcount(gray(i) ^ gray((i + 1) % size)) == 1);
            assert(grayInverse(gray(i)) == i);
        }
        for (bool s : seen) assert(s);
    }

    assert(singleNumberII({2, 2, 3, 2}) == 3 && singleNumberIIBits({2, 2, 3, 2}) == 3);
    assert(singleNumberII({-4, 1, 1, 1}) == -4 && singleNumberIIBits({-4, 1, 1, 1}) == -4);
    mt19937 rng(7);
    for (int t = 0; t < 300; t++) {
        int32_t single = int32_t(rng());
        vector<int32_t> nums;
        for (int j = 0; j < 5; j++) {
            int32_t v = int32_t(rng());
            if (v == single) v ^= 1;
            nums.insert(nums.end(), {v, v, v});
        }
        nums.push_back(single);
        shuffle(nums.begin(), nums.end(), rng);
        assert(singleNumberII(nums) == single && singleNumberIIBits(nums) == single);
    }

    cout << "gray(0..7):";
    for (uint32_t g : first8) cout << ' ' << g;
    cout << "\nall Gray code and Single Number II tests passed\n";
}
function gray(i: number): number {
  return (i ^ (i >>> 1)) >>> 0;
}

function grayInverse(g: number): number {
  let i = 0;
  for (; g !== 0; g >>>= 1) i ^= g;
  return i >>> 0;
}

function singleNumberIIBits(nums: number[]): number {
  let result = 0;
  for (let b = 0; b < 32; b++) {
    let count = 0;
    for (const x of nums) count += (x >>> b) & 1;
    if (count % 3 !== 0) result |= 1 << b; // 1 << 31 is the sign bit: negatives come out right
  }
  return result;
}

function singleNumberII(nums: number[]): number {
  let ones = 0;
  let twos = 0;
  for (const x of nums) {
    ones = (ones ^ x) & ~twos;
    twos = (twos ^ x) & ~ones;
  }
  return ones;
}

function popcount(x: number): number {
  let c = 0;
  for (; x !== 0; x &= x - 1) c++;
  return c;
}

function check(ok: boolean, what: string): void {
  if (!ok) throw new Error("check failed: " + what);
}

const first8 = [0, 1, 2, 3, 4, 5, 6, 7].map(gray);
check(first8.join() === "0,1,3,2,6,7,5,4", "gray table");
check(grayInverse(6) === 4 && grayInverse(11) === 13, "gray inverse");
for (let bits = 1; bits <= 10; bits++) {
  const size = 1 << bits;
  const seen = new Set<number>();
  for (let i = 0; i < size; i++) {
    seen.add(gray(i));
    check(popcount(gray(i) ^ gray((i + 1) % size)) === 1, "one-bit step");
    check(grayInverse(gray(i)) === i, "inverse");
  }
  check(seen.size === size, "every pattern");
}

check(singleNumberII([2, 2, 3, 2]) === 3 && singleNumberIIBits([2, 2, 3, 2]) === 3, "II example");
check(singleNumberII([-4, 1, 1, 1]) === -4 && singleNumberIIBits([-4, 1, 1, 1]) === -4, "II negative");
let seed = 7;
const rand32 = (): number => {
  seed = (Math.imul(seed, 1103515245) + 12345) | 0; // simple LCG, signed 32-bit
  return seed;
};
for (let t = 0; t < 300; t++) {
  const single = rand32();
  const nums: number[] = [];
  for (let j = 0; j < 5; j++) {
    let v = rand32();
    if (v === single) v ^= 1;
    nums.push(v, v, v);
  }
  nums.push(single);
  check(singleNumberII(nums) === single && singleNumberIIBits(nums) === single, "II random");
}

console.log("gray(0..7):", first8.join(" "));
console.log("all Gray code and Single Number II tests passed");

Bit Manipulation in System Design

Bloom Filters

A bloom filter uses hash functions that each set a bit in a bit array of size . To check membership, verify all bits are set. False positives are possible; false negatives are not.

graph TD
    subgraph "Bloom Filter (m=10 bits)"
        B["0|1|1|0|0|1|0|0|1|0"]
    end
    H1["h1('cat') = 1"] --> B
    H2["h2('cat') = 2"] --> B
    H3["h3('cat') = 5"] --> B

The false positive probability for inserted elements:

Optimal number of hash functions:

TypeScript:

class BloomFilter {
  private bits: Uint8Array;
  private size: number;
  private hashCount: number;

  constructor(size: number, hashCount: number) {
    this.size = size;
    this.hashCount = hashCount;
    this.bits = new Uint8Array(Math.ceil(size / 8));
  }

  private hash(value: string, seed: number): number {
    let h = seed;
    for (let i = 0; i < value.length; i++) {
      h = (h * 31 + value.charCodeAt(i)) & 0x7fffffff;
    }
    return h % this.size;
  }

  add(value: string): void {
    for (let i = 0; i < this.hashCount; i++) {
      const idx = this.hash(value, i + 1);
      this.bits[idx >> 3] |= 1 << (idx & 7);
    }
  }

  mightContain(value: string): boolean {
    for (let i = 0; i < this.hashCount; i++) {
      const idx = this.hash(value, i + 1);
      if (!(this.bits[idx >> 3] & (1 << (idx & 7)))) {
        return false; // definitely not present
      }
    }
    return true; // possibly present
  }
}

The bit addressing is the pattern behind every packed bit array: bit idx lives in byte idx >> 3 (idx / 8) at position idx & 7 (idx % 8); with 64-bit words, idx >> 6 and idx & 63. Sizing (about 9.6 bits per element for 1% false positives) and variants are in Probabilistic Data Structures.

Feature Flags with Bitmasks

Use individual bits to represent feature toggles. A single 32-bit integer can store 32 boolean flags.

TypeScript:

enum Feature {
  DARK_MODE    = 1 << 0,  // 1
  BETA_UI      = 1 << 1,  // 2
  NEW_CHECKOUT = 1 << 2,  // 4
  AI_SEARCH    = 1 << 3,  // 8
}

class FeatureFlags {
  private flags: number;

  constructor(flags = 0) {
    this.flags = flags;
  }

  enable(feature: Feature): void {
    this.flags |= feature;
  }

  disable(feature: Feature): void {
    this.flags &= ~feature;
  }

  isEnabled(feature: Feature): boolean {
    return (this.flags & feature) !== 0;
  }

  toggle(feature: Feature): void {
    this.flags ^= feature;
  }
}

Python:

from enum import IntFlag

class Feature(IntFlag):
    DARK_MODE    = 1 << 0
    BETA_UI      = 1 << 1
    NEW_CHECKOUT = 1 << 2
    AI_SEARCH    = 1 << 3

class FeatureFlags:
    def __init__(self, flags: int = 0):
        self.flags = flags

    def enable(self, feature: Feature) -> None:
        self.flags |= feature

    def disable(self, feature: Feature) -> None:
        self.flags &= ~feature

    def is_enabled(self, feature: Feature) -> bool:
        return bool(self.flags & feature)

    def toggle(self, feature: Feature) -> None:
        self.flags ^= feature

The same pattern runs real APIs: POSIX open(path, O_WRONLY | O_CREAT | O_TRUNC, 0644) ORs option bits together; Linux capabilities (CAP_NET_BIND_SERVICE, …) are bit positions in 64-bit sets shown as hex masks in /proc/<pid>/status; Discord stores a role's permissions as one big integer of bit flags, serialised as a string in JSON so it can grow past JavaScript's 53-bit safe-integer range. Checking "has all of these flags" is (flags & need) == need; "has any" is (flags & need) != 0. Mixing them up is a classic authorisation bug.

TypeScript note

TypeScript enum is not "erasable" syntax, so type-stripping runtimes (Node's built-in TypeScript support) reject the snippet above; an as const object works everywhere. JavaScript flags top out at 31 bits before the sign bit interferes; beyond that, use BigInt.

Unix File Permissions

The classic real-world bit manipulation example: rwxr-xr-- = 111 101 100 = 0754.

Linux file modes in full

The permission bits are only the bottom 9 bits of a file's mode (st_mode from stat(2)). Above them sit setuid (04000), setgid (02000) and sticky (01000) — /tmp is 01777 — and the 4-bit file type under the mask S_IFMT (0170000): 0100000 regular file, 0040000 directory, 0120000 symlink. So "is it a directory?" is (mode & S_IFMT) == S_IFDIR, and the umask is applied with AND-NOT: a file requested as 0666 under umask 0022 gets 0666 & ~0022 = 0644. See File Systems and Process Security.

Chess bitboards

A chessboard has 64 squares and a word has 64 bits. A bitboard is a 64-bit integer where bit means "square has the property"; an engine keeps one per piece type and colour. With a1 = 0 … h8 = 63: empty squares are ~(white | black); all white single pawn pushes are (whitePawns << 8) & empty; knight moves are shifts by ±6, ±10, ±15, ±17, each AND-ed with a file mask such as notAFile = ~0x0101010101010101 to drop moves that wrapped around the edge; mobility is a popcount; and pieces are iterated with ctz plus bb &= bb - 1. Sliding pieces use magic bitboards (multiply the occupancy by a precomputed constant, shift, and index an attack table). Stockfish and most strong engines are bitboard-based; see the Chess Programming Wiki.

Database bitmap indexes

A bitmap index keeps, for each distinct value of a column, one bit per row. WHERE color = 'red' AND size = 'L' becomes an AND of two bitmaps and COUNT(*) a popcount, 64 rows per instruction. They suit low-cardinality columns in read-heavy analytics (Oracle has offered them since the 1990s). PostgreSQL builds bitmaps on the fly in a bitmap heap scan, combining indexes with BitmapAnd/BitmapOr (Query Planning & Optimization, Indexing Deep Dive). Sparse bitmaps are compressed: Roaring bitmaps (Chambi, Lemire, Kaser and Godin, 2016) store each -value chunk as a sorted array, a bitmap or runs, whichever is smallest, and are used by Apache Lucene, Druid and Spark. Redis exposes raw bitmaps with SETBIT and BITCOUNT (Redis Internals).

Compression and binary encodings

  • Varints. Protocol Buffers store integers 7 bits per byte, with 0x80 set when more bytes follow: 300 = 100101100 becomes 0xAC 0x02. WebAssembly and DWARF use the same scheme (LEB128).
  • ZigZag. Protobuf's sint32 maps to (n << 1) ^ (n >> 31) so that 0, −1, 1, −2 become 0, 1, 2, 3 and small negatives stay short; decode with (z >>> 1) ^ -(z & 1).
  • Bit streams. Huffman coders (Greedy Algorithms) emit codes that are not byte-aligned, so they OR codes into a 64-bit buffer and flush whole bytes. DEFLATE packs Huffman codes in the opposite bit order from its other fields, so decoders reverse codes — the Reverse Bits trick.
  • Elsewhere: Java's HashMap uses power-of-two capacities and (n - 1) & hash instead of % (Hash Tables); subnet tests are (addr & mask) == network (IP Addressing & Subnetting); RAID-5 rebuilds a lost disk by XOR-ing the survivors with parity.

Language pitfalls

The shift table above covers widths, shifts and overflow. Three more traps:

PitfallPythonJavaC++JavaScript
x & 1 == 0(x & 1) == 0 — correctcompile errorx & (1 == 0) — always 0x & (1 == 0) — always 0
~x meant as unsignednegative; mask with & 0xFFFFFFFFnegative; use >>> or longfine on uint32_tnegative; ~x >>> 0
Narrow types—byte sign-extends: (byte)0x80 >>> 4 is 0x0FFFFFF8uint8_t promotes to int: ~uint8_t(0) is −1—

C, C++ and JavaScript inherited a precedence table where == binds tighter than &, |, ^ (a leftover from C's predecessor B, as Dennis Ritchie explains in The Development of the C Language, 1993). Parenthesise every bitwise sub-expression.

Pitfalls & edge cases

  • Zero. 0 & -0 is 0, __builtin_ctz(0) is undefined, Gosper's hack divides by zero, and n & (n-1) == 0 calls 0 a power of two unless you add n > 0.
  • INT_MIN. Its negation overflows; it is the one negative number with a single set bit.
  • Width. ~0 is 32 ones for int, 64 for long, infinitely many in Python. The literal 0xFFFFFFFF is −1 in Java.
  • Python negatives have infinitely many 1s: while n: n >>= 1 never ends, and bin(-5) is '-0b101', not a bit pattern.
  • Loop bounds. mask < (1 << n), not <=; bits are 0 .. n-1; the submask loop skips the empty set.
  • Endianness is not bit order. Byte order matters only when reinterpreting bytes from files or the network, never for shifts on a value.
  • Memory. dp[1 << 20][20] of 8-byte numbers is about 168 MB.

Variations

  • Popcount relatives: parity, leading zeros (clz, Math.clz32), bit_length, next power of two (1 << bit_length(x - 1)).
  • Morton / Z-order codes interleave the bits of and for 2-D locality (geohashes, Spatial Trees).
  • XOR linear basis (Gaussian elimination over GF(2)) for maximum subset XOR.
  • SOS DP, Broken Profile DP, and meet in the middle (two halves of masks for ).

Cheat Sheet

TrickExpressionPurpose
Check if evenn & 1 == 0Faster than n % 2
Check power of 2n & (n-1) == 0Single set bit
Get lowest set bitn & (-n)Isolate rightmost 1
Clear lowest set bitn & (n-1)Used in popcount
Set bit `n(1 << i)`
Clear bit n & ~(1 << i)Turn off bit
Toggle bit n ^ (1 << i)Flip bit
Check bit (n >> i) & 1Read bit
All 1s (n bits)(1 << n) - 1Mask creation
Swapa ^= b; b ^= a; a ^= bNo temp variable

Reading the cheat sheet in C, C++, Java and JavaScript

In C, C++ and JavaScript type these as (n & 1) == 0 and (n & (n - 1)) == 0 — == binds tighter than & there (Python parses them correctly). "Faster than n % 2" is mostly historical (compilers emit the same instruction), but n & 1 is also correct for negative odd numbers, where n % 2 == 1 is not.

More one-liners:

TrickExpression
Mask of lowest set bit and belowx ^ (x - 1)
Turn off the trailing block of 1sx & (x + 1)
Next submask / next superset(s - 1) & m / (s + 1) | m
Next combination (Gosper)c = x & -x; r = x + c; (((r ^ x) >> 2) / c) | r
Gray codei ^ (i >> 1)
XOR of 0..n[n, 1, n + 1, 0][n % 4]
Round up to a multiple of 8(x + 7) & ~7

Practice Problems

ProblemTechniqueDifficulty
Single NumberXOR all elementsEasy
Number of 1 BitsBrian Kernighan'sEasy
Power of Twon & (n-1)Easy
Reverse BitsBit-by-bit extractionEasy
Missing NumberXOR with indicesEasy
Single Number II (appears 3x)Bit counting per positionMedium
SubsetsBitmask enumerationMedium
Counting Bits (0 to n)DP with i & (i-1)Medium
Maximum XOR of Two NumbersTrie + greedyMedium
Minimum Number of FlipsXOR + popcountMedium

The table above is a quick index. (The last row refers to LeetCode 1318, "Minimum Flips to Make a OR b Equal to c".) The practice ladder below orders the problems from easiest to hardest, with links, hints and full solutions for the key ones.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

  1. Number of 1 Bits (LeetCode 191) — popcount of a 32-bit value. Hint: Kernighan; in Java loop while n != 0, since the input may be negative.
  2. Single Number (LeetCode 136) — one value without a twin. Hint: XOR everything.
  3. Missing Number (LeetCode 268) — distinct numbers from , one absent. Hint: XOR all indices and all values.
  4. Reverse Bits (LeetCode 190) — mirror 32 bits. Hint: loop exactly 32 times; >>> in Java/JS.
  5. Counting Bits (LeetCode 338) — popcount of in . Hint: ans[i] = ans[i >> 1] + (i & 1).
  6. Sum of Two Integers (LeetCode 371) — add without + or -. Hint: XOR is the carry-less sum; (a & b) << 1 is the carry.
  7. Subsets (LeetCode 78) — every subset of distinct numbers. Hint: masks , or backtracking.
  8. Apple Division (CSES 1623) — split up to 20 weights into two groups with the smallest difference. Hint: try all masks; in Python build subset sums incrementally with sums[m] = sums[m & (m - 1)] + w[ctz(m)].
  9. Gray Code (LeetCode 89) — a cyclic one-bit-change sequence. Hint: i ^ (i >> 1).
  10. Single Number II (LeetCode 137) — everything three times except one. Solution: the Implementation section, both methods.
  11. Single Number III (LeetCode 260) — two values without twins. Hint: split on the lowest set bit of the total XOR; mind -INT_MIN in C++.
  12. Bitwise AND of Numbers Range (LeetCode 201) — AND of every integer in .
  13. Maximum XOR of Two Numbers in an Array (LeetCode 421) — largest a[i] ^ a[j].
  14. Number of Valid Words for Each Puzzle (LeetCode 1178) — count words whose letters fit inside a 7-letter puzzle and include its first letter.
Solution: Sum of Two Integers (371)

Repeat "sum = XOR, carry = AND shifted left" until no carry is left. Python needs a 32-bit mask, or negative inputs loop forever. Each round pushes the lowest carry at least one place left, so there are at most 32 rounds.

def get_sum(a: int, b: int) -> int:
    MASK = 0xFFFFFFFF
    a &= MASK
    b &= MASK
    while b:
        a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK
    return a if a < 0x80000000 else a - (1 << 32)


assert get_sum(1, 2) == 3 and get_sum(-2, 3) == 1 and get_sum(-5, -7) == -12
Solution: Bitwise AND of Numbers Range (201)

Below the highest bit where and differ, every bit takes both values somewhere in the range, so it ANDs to 0. The answer is the common prefix of and ; clearing the lowest set bit of until finds it.

def range_bitwise_and(left: int, right: int) -> int:
    while right > left:
        right &= right - 1
    return right


assert range_bitwise_and(5, 7) == 4 and range_bitwise_and(0, 0) == 0
assert range_bitwise_and(1, 2147483647) == 0
Solution: Maximum XOR of Two Numbers (421)

Decide the answer's bits from the top. Try to extend the best prefix with a 1, and check with a set of prefixes whether two numbers realise it (if then ). The XOR trie does the same greedy per number.

def find_maximum_xor(nums: list[int]) -> int:
    ans = 0
    for bit in range(30, -1, -1):
        want = ans | (1 << bit)
        prefixes = {x >> bit for x in nums}
        if any((p ^ (want >> bit)) in prefixes for p in prefixes):
            ans = want
    return ans


assert find_maximum_xor([3, 10, 5, 25, 2, 8]) == 28
Solution: Number of Valid Words for Each Puzzle (1178)

Count words by 26-bit letter mask. A word fits a puzzle iff its mask is a submask of the puzzle's mask containing the first letter. Enumerate the submasks of the other six letters and add the first letter: 64 lookups per puzzle.

from collections import Counter


def find_num_of_valid_words(words: list[str], puzzles: list[str]) -> list[int]:
    def mask_of(s: str) -> int:
        m = 0
        for ch in s:
            m |= 1 << (ord(ch) - ord("a"))
        return m

    freq = Counter(mask_of(w) for w in words)
    out = []
    for p in puzzles:
        first = 1 << (ord(p[0]) - ord("a"))
        rest = mask_of(p) & ~first
        total, s = 0, rest
        while True:                      # every submask of rest, including 0
            total += freq.get(s | first, 0)
            if s == 0:
                break
            s = (s - 1) & rest
        out.append(total)
    return out


words = ["aaaa", "asas", "able", "ability", "actt", "actor", "access"]
puzzles = ["aboveyz", "abrodyz", "abslute", "absoryz", "actresz", "gaswxyz"]
assert find_num_of_valid_words(words, puzzles) == [1, 1, 3, 2, 4, 0]

Common mistakes & interview follow-ups

"Why does n & (n - 1) clear the lowest set bit?" Draw and . Interviewers want the picture.

"Single Number II without a loop over bits?" Derive the ones/twos automaton; generalise to " times except one" with counter words.

"Does it handle negatives?" Python: convert bit 31 back to a sign; Kernighan never ends on negatives. Java: >> vs >>>. C++: use unsigned.

"All subsets of size without generating ?" Gosper's hack, with its derivation.

"Cost of iterating submasks of all masks?" by the three-labels argument; "only need sums?" → SOS DP, .

"Max XOR faster than ?" Bit-greedy with a set or trie, ; subarray → prefix XOR + trie; subset → linear basis.

"Store a million booleans?" A bitset: 125 KB instead of ~1 MB of bools.

Mistakes interviewers watch for: missing parentheses around &; 1 << 31 and 1 << 40; forgetting n > 0; Python infinite loops on negatives; forgetting the empty subset; >> where >>> was needed; assuming % and >> agree on negatives.

Try It Yourself

Problem 1: Determine if 64 is a power of 2 using bit manipulation.

Solution

Use the formula: n > 0 && (n & (n-1)) == 0.

  • 64 in binary: 01000000
  • 63 in binary: 00111111
  • 64 & 63 = 00000000 = 0 Since 64 > 0 and the result is 0, 64 is a power of 2.

Problem 2: Given the array [4, 1, 2, 1, 2], find the element that appears only once using XOR.

Solution

XOR all elements: 4 ^ 1 ^ 2 ^ 1 ^ 2.

  • 1 ^ 1 = 0 (duplicates cancel)
  • 2 ^ 2 = 0 (duplicates cancel)
  • 4 ^ 0 ^ 0 = 4 Answer: 4. Time: , Space: .

Problem 3: Count the number of set bits (1s) in the binary representation of 29.

Solution

29 in binary: 11101. Use Brian Kernighan's algorithm:

  • 29 & 28 = 11101 & 11100 = 11100 (28). count=1
  • 28 & 27 = 11100 & 11011 = 11000 (24). count=2
  • 24 & 23 = 11000 & 10111 = 10000 (16). count=3
  • 16 & 15 = 10000 & 01111 = 00000 (0). count=4 Answer: 4 set bits.

Problem 4: Using bitmask, represent the subset {0, 2, 4} of the set {0, 1, 2, 3, 4}. What is the bitmask value?

Solution

Set bit 0, bit 2, and bit 4:

  • Bit 0: 1 << 0 = 00001 = 1
  • Bit 2: 1 << 2 = 00100 = 4
  • Bit 4: 1 << 4 = 10000 = 16
  • Bitmask = 1 | 4 | 16 = 10101 = 21 To check if element 3 is in the subset: 21 & (1 << 3) = 21 & 8 = 0 → No.

Problem 5: Swap the values a = 5 and b = 9 using only XOR operations, without a temporary variable.

Solution
  • a = 5 (0101), b = 9 (1001)
  • Step 1: a = a ^ b = 0101 ^ 1001 = 1100 (12)
  • Step 2: b = b ^ a = 1001 ^ 1100 = 0101 (5) → b is now original a
  • Step 3: a = a ^ b = 1100 ^ 0101 = 1001 (9) → a is now original b Result: a = 9, b = 5.

Problem 6: List the submasks of 13 (1101) in the order the loop s = (s - 1) & m produces them.

Solution

13 → 12 → 9 → 8 → 5 → 4 → 1 → 0. That is submasks, because 13 has three set bits. Step 13 → 12: 1100 & 1101. Step 8 → 5: 0111 & 1101 = 0101.

Problem 7: Using Gosper's hack, what comes after 14 (01110)?

Solution

c = 14 & -14 = 2, r = 14 + 2 = 16 (10000), r ^ x = 11110 (30), 30 >> 2 = 7, 7 / 2 = 3 (00011), 3 | 16 = 19 (10011). Check: 19 has three set bits and no number between 15 and 18 does (15 has four; 16, 17 and 18 have one or two).

Problem 8: What is the 4-bit Gray code of 11, and what number has Gray code 11?

Solution

$g(11) = 11 \oplus 5 = $ 1011 ⊕ 0101 = 1110 = 14. Inverse of 11: $11 \oplus 5 \oplus 2 \oplus 1 = $ 1011 ⊕ 0101 ⊕ 0010 ⊕ 0001 = 1101 = 13, and indeed .

Quick Quiz

1. What does the expression n & (n - 1) do?

  • a) Checks if is even
  • b) Clears the lowest set bit of
  • c) Sets the lowest bit of
  • d) Counts the number of set bits
Answer

b) Clears the lowest set bit of — Subtracting 1 flips all bits from the lowest set bit downward. ANDing with the original clears that lowest set bit. This is the basis of Brian Kernighan's popcount algorithm.

2. What is the result of n & (-n)?

  • a) The highest set bit of
  • b) The lowest set bit of (isolated)
  • c) The complement of
  • d) Zero
Answer

b) The lowest set bit of (isolated) — In two's complement, . ANDing with isolates the rightmost set bit. This is used in Fenwick trees for index arithmetic.

3. What key property of XOR makes the "single number" problem solvable in space?

  • a) XOR is commutative
  • b) (self-cancellation) and (identity)
  • c) XOR is faster than addition
  • d) XOR distributes over AND
Answer

b) (self-cancellation) and (identity) — XORing all elements cancels out every duplicate pair, leaving only the unique element.

4. For bitmask DP problems like the Traveling Salesman Problem, what limits the practical input size?

  • a) The number of edges
  • b) The number of states is , which grows exponentially with
  • c) The weight of the edges
  • d) The memory bandwidth
Answer

b) The number of states is , which grows exponentially with — The bitmask has possible values and each is combined with possible current positions, giving states. This is only feasible for or so.

5. How are Unix file permissions represented using bit manipulation?

  • a) As a string of characters
  • b) Using 3 groups of 3 bits each (owner, group, other) where each group encodes read, write, execute
  • c) As a hash map
  • d) Using a linked list of permissions
Answer

b) Using 3 groups of 3 bits each (owner, group, other) where each group encodes read, write, execute — For example, rwxr-xr-- = 111 101 100 = octal 754. Each permission is a single bit: read (4), write (2), execute (1).

6. In Java, what is 1 << 40?

Answer
  1. For an int, Java uses only the low 5 bits of the shift count, so 1 << 40 is 1 << (40 & 31) = 1 << 8. Write 1L << 40 for . JavaScript behaves the same way; in C++ the expression is undefined behaviour.

7. How many (mask, submask) pairs exist for ?

Answer

. Each of the four elements is either outside the mask, in the mask but not the submask, or in both.

8. Why does ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones find the value that appears once when all others appear three times?

Answer

Per bit position, (ones, twos) is a counter that cycles 0 → 1 → 2 → 0 on every 1 bit it sees. Bits from tripled values return the counter to its starting state, so at the end each position's counter is 1 exactly where the single value has a 1, and that state is stored in ones.

Further Reading

More Archon pages: How Computers Work (how bits become circuits) · Data Structures in Memory (words, alignment, cache lines) · Fenwick Trees (i & -i in action) · Tries in Depth (the XOR trie) · Probabilistic Data Structures (Bloom filters, HyperLogLog's leading-zero counts) · Prefix Sums (prefix XOR) · Backtracking & Recursion (the recursive alternative to mask enumeration) · Bitmask DP · SOS DP.

Sources:

Lessons: previous — Greedy Algorithms · next — Randomized Algorithms · module — Paradigms · course — DSA: Zero to Mastery.