Bit manipulation — XOR tricks, LSB, counting set bits

3.7.20 · Coding › Algorithm Paradigms

1. Bit model (first principles)

Ek unsigned integer $x$ base 2 mein likha jaata hai: $x = \sum_{i = 0}^{n - 1} b_{i} 2^{i}, b_{i} \in {0, 1}$ Bit $i$ ki place value $2^{i}$ hoti hai. Bit $0$ sabse rightmost hai = Least Significant Bit (LSB).

Negative numbers two's complement use karte hain: $- x = (\neg x) + 1$ (saare bits flip karo, 1 add karo). Yahi ek fact hai jo neeche x & -x trick ka secret hai.

2. XOR — cancellation engine

XOR truth table: 0^0=0, 1^1=0, 0^1=1, 1^0=1. Bit 1 hai ⟺ inputs differ karte hain.

Teen laws seedhe table se derive karo:

Identity: $a \oplus 0 = a$ (0 ke saath XOR karne se bits unchanged rehti hain — kuch apne aap se differ nahi karta, sivaay jahan $a = 1$ aur $0$ ho... check: $1 \oplus 0 = 1, 0 \oplus 0 = 0$ ✓).
Self-inverse: $a \oplus a = 0$ (har bit apne aap ke barabar hai → saare "differ" tests false hain).
Commutative & associative: kyunki har bit independent hai, order matter nahi karta.

Worked example Temp variable ke bina swap karo

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)

Yeh step kyun? Har line self-inverse use karke ek original value peel off karti hai. (Use mat karo agar a aur b same memory location par ho — woh zero out ho jaata hai.)

3. LSB tricks — `x & -x`

Derive karo. Maano lowest set bit position $k$ par hai, toh $x = high bits a 1 k zeros 0 \dots 0$ Two's complement: $- x = \neg x + 1$ . Flip karne se $\overset{a}{ˉ} 01 \dots 1$ milta hai; 1 add karne se trailing ones mein ripple hota hai: $- x = \overset{a}{ˉ} 1 k 0 \dots 0$ Ab AND karo. High bits: $a & \overset{a}{ˉ} = 0$ . Position $k$ : $1 & 1 = 1$ . Trailing: $0 & 0 = 0$ . $x & - x = 2^{k}$ — exactly isolated lowest set bit.

4. Set bits count karna (popcount)

Formula Naive loop —

$O (bits)$

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

Kyun? LSB read karo, phir right shift karo taaki next bit expose ho.

Formula Brian Kernighan —

$O (# set bits)$

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

Kyun faster? har iteration ek set bit ko kill karta hai (section 3), toh loop utni baar hi chalta hai jitne 1s hain — sparse numbers ke liye great.

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

5. Common mistakes (steel-manned)

Flashcards

LSB kya hai aur uski place value?

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 ho jaate hain).

Woh element kaise dhundein jo ek baar appear karta hai jab baaki sab do baar appear karte hain?

Poora array XOR karo; pairs cancel hote hain, unique value bachti hai.

O (n)

O (1)

x & -x kya compute karta hai, aur kyun?

Lowest set bit (

2^{k}

) isolate karta hai; two's complement us bit ko aligned rakhta hai aur upar sab cancel kar deta hai.

x & (x-1) kya karta hai?

Lowest set bit clear karta hai.

Power of two test?

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

Brian Kernighan popcount complexity?

O (# set bits)

— har loop mein ek set bit remove hoti hai.

x << k aur x >> k arithmetically kya hain?

x \cdot 2^{k}

aur

⌊ x / 2^{k} ⌋

0..n mein missing number XOR se kaise dhundein?

Saare indices 0..n ko array ke saare elements ke saath XOR karo; missing value survive karti hai.

XOR swap aliased variables ke liye kyun fail karta hai?

a ^= a value zero kar deta hai, toh dono 0 ho jaate hain.

Recall Feynman: ek 12-saal ke bachche ko explain karo

Ek row light switches imagine karo. XOR ek magic toggle hai: kisi switch ko do baar flip karo aur aisa lagta hai jaise tune chhua hi nahi — toh jo bhi number even number of times aata hai woh gayab ho jaata hai, aur sirf odd wala chalta rahta hai glowing. x & -x ek flashlight hai jo lowest switch dhundti hai jo ON hai. Aur kitne lights ON hain ginne ke liye, Brian Kernighan ka trick baar baar lowest ON light band karta jaata hai aur count karta hai kitni baar kiya.

Connections

Two's Complement Representation — kyun -x aisa behave karta hai.
Hash Sets vs O(1)-space tricks — XOR ek memoryless alternative ke roop mein.
Bitmask Dynamic Programming — subsets as integers.
Logarithms and Powers of Two
Greedy and Divide-and-Conquer (Algorithm Paradigms)