Bit manipulation — XOR tricks, LSB, counting set bits

1. The bit model (first principles)

An unsigned integer $x$ is written in base 2: $x = \sum_{i=0}^{n-1} b_i \, 2^i, \qquad b_i \in \{0,1\}$ Bit $i$ has place value $2^i$ . Bit $0$ is the rightmost = Least Significant Bit (LSB).

Negative numbers use two's complement: $-x = (\lnot x) + 1$ (flip all bits, add 1). This single fact is the secret behind the x & -x trick below.

2. XOR — the cancellation engine

XOR truth table: 0^0=0, 1^1=0, 0^1=1, 1^0=1. Bit is 1 ⟺ inputs differ.

Derive its three laws straight from the table:

Identity: $a \oplus 0 = a$ (XOR with 0 leaves bits unchanged — nothing differs from itself except where $a=1$ and $0$ ... check: $1\oplus0=1, 0\oplus0=0$ ✓).
Self-inverse: $a \oplus a = 0$ (every bit equals itself → all "differ" tests are false).
Commutative & associative: since each bit is independent, order doesn't matter.

Worked example Swap without a temp variable

a ^= b;   // a now holds a^b
b ^= a;   // b = b^(a^b) = a   (b cancels)
a ^= b;   // a = (a^b)^a = b   (a cancels)

Why this step? Each line uses self-inverse to peel off one original value. (Don't use if a and b are the same memory location — it zeros out.)

3. LSB tricks — `x & -x`

Derive it. Let the lowest set bit be at position $k$ , so $x = \underbrace{\,a\,}_{\text{high bits}}\,1\,\underbrace{0\cdots0}_{k \text{ zeros}}$ Two's complement: $-x = \lnot x + 1$ . Flipping gives $\bar a\,0\,1\cdots1$ ; adding 1 ripples through the trailing ones: $-x = \bar a\,1\,\underbrace{0\cdots0}_{k}$ Now AND them. High bits: $a \,\&\, \bar a = 0$ . Position $k$ : $1\,\&\,1 = 1$ . Trailing: $0\,\&\,0=0$ . $\boxed{\,x \,\&\, -x \;=\; 2^k\,}$ — exactly the isolated lowest set bit.

4. Counting set bits (popcount)

Formula Naive loop —

$O(\text{bits})$

count = 0
while x: count += x & 1; x >>= 1

Why? read LSB, then shift right to expose the next bit.

Formula Brian Kernighan —

$O(\#\text{set bits})$

count = 0
while x: x &= x - 1; count += 1

Why faster? each iteration kills one set bit (section 3), so it loops only as many times as there are 1s — great for sparse numbers.

Figure — Bit manipulation — XOR tricks, LSB, counting set bits

5. Common mistakes (steel-manned)

Flashcards

What is the LSB and its place value?

The least significant (rightmost) bit, place value

2^0 = 1

XOR identity law?

a \oplus 0 = a

XOR self-inverse law?

a \oplus a = 0

(duplicates cancel).

How to find the element appearing once when all others appear twice?

XOR the whole array; pairs cancel, the unique value remains.

O(n)

O(1)

What does x & -x compute, and why?

Isolates the lowest set bit (

2^k

); two's complement keeps that bit aligned and cancels everything above.

What does x & (x-1) do?

Clears the lowest set bit.

Test for a power of two?

x != 0 && (x & (x-1)) == 0.

Brian Kernighan popcount complexity?

O(\#\text{set bits})

— one set bit removed per loop.

x << k and x >> k equal what arithmetically?

x \cdot 2^k

and

\lfloor x/2^k\rfloor

Find the missing number in 0..n with XOR?

XOR all indices 0..n with all array elements; the missing value survives.

Why does XOR swap fail for aliased variables?

a ^= a zeros the value, so both end up 0.

Recall Feynman: explain to a 12-year-old

Imagine a row of light switches. XOR is a magic toggle: flip a switch twice and it's like you never touched it — so any number that shows up an even number of times disappears, and only the odd one is left glowing. x & -x is a flashlight that finds the lowest switch that's ON. And to count how many lights are on, Brian Kernighan's trick keeps turning off the lowest ON light one at a time and tallies how many times it did that.

Connections

Two's Complement Representation — why -x behaves as it does.
Hash Sets vs O(1)-space tricks — XOR as a memoryless alternative.
Bitmask Dynamic Programming — subsets as integers.
Logarithms and Powers of Two
Greedy and Divide-and-Conquer (Algorithm Paradigms)

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, integer matlab sirf 0 aur 1 ka ek row — bits. Bit manipulation ka matlab hai un switches ko seedha chhedna, slow arithmetic ke bajaye. Teen main hathiyaar hain. Pehla XOR (^): jo bhi cheez do baar (even times) aaye, woh khud cancel ho jaati hai (a^a=0), aur a^0=a rehta hai. Isi se "array me sab elements do-do baar hain, ek single hai" wala problem ek hi loop me ho jaata hai — pure array ko XOR kar do, jo bacha woh answer.

Doosra trick: x & -x sabse neeche wala set bit (LSB jo ON hai) nikaal deta hai. Yeh two's complement ki wajah se kaam karta hai — -x matlab saare bits flip karke +1, isse lowest 1 bit exactly line up ho jaata hai aur upar sab cancel. Aur x & (x-1) sabse neeche wala set bit hata deta hai — isi se power-of-two check (x & (x-1) == 0) banta hai.

Teesra: set bits ginna (popcount). Naive way me har bit shift karke gino. Lekin Brian Kernighan ka trick smart hai — x &= x-1 har baar ek set bit udaata hai, toh loop sirf utni baar chalega jitne 1s hain. Sparse numbers ke liye bahut fast.

Yeh sab isliye important hai kyunki interview aur competitive coding me yeh tricks $O(n)$ ya $O(1)$ space me kaam karwa dete hain, bina extra hash set ke. Bas yaad rakho: XOR copies ko maarta hai, AND-minus low bit pakadta hai, minus-one low bit girata hai.

Bit manipulation — XOR tricks, LSB, counting set bits

1. The bit model (first principles)

2. XOR — the cancellation engine

3. LSB tricks — `x & -x`

4. Counting set bits (popcount)

5. Common mistakes (steel-manned)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Algorithm Paradigms

Connections