Bit Manipulation

Every integer is already an array of bits, and the CPU can process all of them in one instruction. Learn a handful of operators and you get flags, sets and subsets almost for free.

beginner⏱ 10 min read

←Builds on

4Generating Subsets & PermutationsA subset of n items is an n-bit number; counting from 0 to 2ⁿ − 1 lists them all.5Fenwick Tree (Binary Indexed Tree)The Fenwick jumps idx += idx & -idx are the lowest set bit trick; this stage explains it in general.

Leads to→

9Fast Exponentiation & Modular ArithmeticThe binary digits of n decide which squares get multiplied in.10Bitmask DPThe set of visited cities is stored as a bitmask, tested and extended with the bit tricks you just learned.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Numbers are rows of bits

In binary, 12 is 1100: bit 3 and bit 2 are on, worth 8 + 4. Bit i is worth 2^i, and we count positions from the right, starting at 0.

The bitwise operators work on every position independently, with no carries:

a & b (AND): 1 only where both bits are 1
a | b (OR): 1 where at least one is 1
a ^ b (XOR): 1 where the bits differ
~a (NOT): flips every bit

So 12 & 10 = 8, 12 | 10 = 14, 12 ^ 10 = 6. XOR has a lovely property: x ^ x = 0 and x ^ 0 = x, so XOR-ing a list where every value appears twice except one leaves exactly the lonely value.

02Shifts and single bit tricks

a << k moves every bit k places left, which multiplies by 2^k; a >> k moves them right, dividing by 2^k and rounding down. In particular 1 << i is a number with a single 1 at position i: a mask.

With a mask you can touch one bit and leave the rest alone:

test: (a >> i) & 1 or a & (1 << i) is nonzero
set: a | (1 << i)
clear: a & ~(1 << i)
toggle: a ^ (1 << i)

Memorise these four lines: they appear in every bitmask solution. One pitfall: in C++ and Java, 1 << 40 overflows a 32-bit int. Write 1LL << 40 (or 1L) when i can reach 31 or more.

03x & (x − 1): drop the lowest 1

Subtracting 1 from x turns its lowest 1 into 0 and every 0 below it into 1; the bits above stay put. AND-ing with the original cancels that whole tail, so x & (x - 1) is x with its lowest set bit removed.

Two classic uses:

count the 1-bits: repeat x &= x - 1 until x is 0. The loop runs once per 1-bit, not once per position.
is x a power of two? Powers of two have exactly one 1, so the test is x > 0 && (x & (x - 1)) == 0.

A sibling trick, x & -x, keeps only the lowest 1. It is the heart of the Fenwick tree. In practice you can also call __builtin_popcount (C++) or Integer.bitCount (Java), but knowing why they work helps you invent your own tricks.

180 = 10110100₂. Subtracting 1 flips the tail starting at the lowest 1; AND keeps only what both agree on.

04Subsets as numbers

Take n items. A number from 0 to 2^n − 1 can describe a subset: bit k is 1 when item k is in. Mask 1011 means items 0, 1 and 3. So one plain loop lists every subset:

for (mask = 0; mask < (1 << n); mask++), and inside, mask & (1 << k) asks whether item k is taken.

Set operations become single instructions: union is |, intersection is &, "add item k" is | (1 << k), size is popcount. This is what makes bitmask DP possible: a state like "which cities have I visited" fits in one integer and can index an array. The price is 2^n states, so it works up to n ≈ 20. That limit returns in the capstone lesson.

Cost at a glance

One bitwise operationO(1)

Popcount with x & (x−1)O(number of 1-bits)

Enumerate all subsetsO(2ⁿ)

Remember

AND keeps common 1s, OR collects all 1s, XOR marks differences, and shifts multiply or divide by powers of two.
The mask 1 << i lets you test, set, clear or toggle a single bit; x & (x−1) removes the lowest 1.
An n-bit number is a subset of n items, so a loop from 0 to 2ⁿ−1 visits every subset; this is the basis of bitmask DP.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the yellow cell: each round, x − 1 flips the tail from the lowest 1 down, and the AND wipes exactly that one bit. Then try op = and, set or subsets.

Interactive visualizerfocus here, then space ← →

Bits: `popcount(182)`

position

x

= 182

Count the 1 bits of 182 = 10110110₂. Instead of looking at all 8 positions, we jump straight from one 1 to the next.

Pseudocode

 1 a & b        // 1 only where both bits are 1 2 a | b        // 1 where at least one bit is 1 3 a ^ b        // 1 where the bits differ 4 a << k, a >> k   // multiply / divide by 2^k 5 mask = 1 << i 6 test: a & mask   set: a | mask   clear: a & ~mask   toggle: a ^ mask 7 count = 0 8 while x != 0: 9   // x - 1 flips the lowest 1 and every 0 below it10   x = x & (x - 1); count += 1   // lowest 1 is gone11 for mask in 0 .. 2^n - 1:12   subset = { item k : mask & (1 << k) != 0 }

1 / 1

Check

Three questions. Pick an answer to see why.

x = 44 = 101100₂. What is x & (x − 1)?

Which expression turns bit i of a OFF and leaves every other bit unchanged?

With n = 5 items, which mask stands for the subset {item 0, item 2, item 4}?

Practice

Real problems to lock it in, easiest first.

LeetCodeNumber of 1 Bits beginner↗LeetCodeSingle Number beginner↗LeetCodeSubsets intermediate↗CSESApple Division intermediate↗CSESGray Code intermediate↗