Bit manipulation — XOR tricks, LSB, counting set bits: Worked examples

3.7.20 · D3 · Coding › Algorithm Paradigms › Bit manipulation — XOR tricks, LSB, counting set bits

The scenario matrix

Is topic ka har problem inhi cells mein se kisi ek mein aata hai. Hum har ek ke liye ek worked example dete hain.

Cell	Kya toot-ta hai / kya test hota hai	Covered by
A. XOR-pairs, positive ints	basic "sab do baar, ek odd" wala	Example 1
B. XOR range, missing element	indices ke saath XOR karo	Example 2
C. XOR splits into two uniques	ek XOR pass kaafi nahi — ek split bit chahiye	Example 3
D. `x & -x` on a positive int	lowest set bit isolate karo	Example 4
E. `x & -x` on a NEGATIVE int	two's complement ka two's complement	Example 5
F. Zero / degenerate input	`x = 0`, single-element array, powers of two	Example 6
G. popcount, dense vs sparse	naive vs Kernighan loop counts	Example 7
H. The "thrice except one" twist	XOR fail ho jaata hai — mod-3 bit counting	Example 8
I. Word problem (real world)	toggling / parity real life mein	Example 9
J. Exam trap	negatives par right-shift, aliased swap	Example 10

Prerequisites jo tumhare paas open ho sakti hain: Two's Complement Representation, Logarithms and Powers of Two, Hash Sets vs O(1)-space tricks.

Cell A — XOR pairs, positive integers

Worked example Example 1 — classic "single number"

Array [7, 3, 5, 3, 7]. Har value do baar aati hai sirf ek ko chhodkar. Loner dhundho.

Forecast: kaun sa number odd-one-out hai? Padhne se pehle guess karo — woh value hai jiska koi twin nahi.

Steps (hum ek running accumulator acc rakhte hain, $0$ se shuru karke):

$a cc = 0 \oplus 7 = 7$ . Yeh step kyun? XOR identity ( $a \oplus 0 = a$ ) matlab $0$ se shuru karna safe hai — yeh sirf pehli value load karta hai.
$a cc = 7 \oplus 3 = 4$ . Kyun? values fold karte raho; order matter nahi karta (XOR commutative hai).
$a cc = 4 \oplus 5 = 1$ . Kyun? same — accumulate karo.
$a cc = 1 \oplus 3 = 2$ . Kyun? doosra 3 pehle 3 ko cancel karna shuru karta hai.
$a cc = 2 \oplus 7 = 5$ . Kyun? doosra 7 pehle 7 ko cancel karna finish karta hai. Jo bhi pair mein tha woh self-destruct ho gaya ( $a \oplus a = 0$ ); sirf 5 bacha.

Answer: 5.

Verify: 7 aur 3 dono even number of times aate hain → contribute $0$ ; sirf 5 odd number of times aata hai → survive karta hai. Kisi bhi order mein paanchon values XOR karne par $5$ aata hai. ✓

Cell B — missing element in a full range

Worked example Example 2 —

0..n mein missing number Array [0, 1, 3, 4] mein 0 se 4 tak ke saare integers hone chahiye the, par ek missing hai. Use dhundho. Yahan $n = 4$ hai.

Forecast: 0,1,2,3,4 mein se kaun sa array mein absent hai?

Steps: 0..4 ke saare indices XOR karo, phir saari array values XOR karo. Present numbers apne range-twin se cancel ho jaate hain; absent wala akela reh jaata hai.

Range XOR: $0 \oplus 1 \oplus 2 \oplus 3 \oplus 4$ . Compute: $0 \oplus 1 = 1$ , $1 \oplus 2 = 3$ , $3 \oplus 3 = 0$ , $0 \oplus 4 = 4$ . To range $= 4$ . Kyun? hum "jo yahan hona chahiye" wala fingerprint bana rahe hain.
Array XOR: $0 \oplus 1 \oplus 3 \oplus 4$ . Compute: $0 \oplus 1 = 1$ , $1 \oplus 3 = 2$ , $2 \oplus 4 = 6$ . To array $= 6$ . Kyun? "jo actually yahan hai" wala fingerprint.
Combine: $4 \oplus 6 = 2$ . Kyun? jo value present hai woh dono fingerprints mein ek-ek baar aati hai → cancel; missing 2 sirf range fingerprint mein hai → survive karta hai.

Answer: 2.

Verify: sanity cross-test ke liye sum check — full range sum $0 + 1 + 2 + 3 + 4 = 10$ ; array sum $0 + 1 + 3 + 4 = 8$ ; $10 - 8 = 2$ . Dono methods agree. ✓

Cell C — two unique numbers (the split-bit trick)

Worked example Example 3 — do elements ek baar aate hain, baaki sab do baar

Array [2, 4, 6, 2, 3, 4]. Do values lonely hain; baaki pairs mein hain. Dono dhundho.

Forecast: ek XOR pass tumhe $u \oplus v$ deta hai (dono loners ek saath mixed). Unhe alag kaise karte ho? Trick guess karo padhne se pehle.

Steps:

Sab kuch XOR karo: $2 \oplus 4 \oplus 6 \oplus 2 \oplus 3 \oplus 4$ . Pairs 2,2 aur 4,4 cancel ho jaate hain, $6 \oplus 3 = 5$ bachta hai. Kyun? yeh $u \oplus v$ hai — dono uniques fuse ho gaye. Inhe abhi alag nahi padh sakte.
5 ka koi ek set bit isolate karo LSB flashlight se: $5 & - 5$ . Since $5 = 10 1_{2}$ , uska lowest set bit $2^{0} = 1$ hai. Yeh step kyun? $u \oplus v$ mein ek set bit ka matlab hai $u$ aur $v$ wahan alag hain — woh bit ek perfect divider hai. Figure dekho.

Array ko do buckets mein split karo: woh values jinmein woh bit set hai vs nahi, har bucket ko alag XOR karo.
- Bit 1 set → {3} (aur us bit ke saath koi pair members). Is bucket ka XOR → 3.
- Bit 1 clear → baaki ka XOR → 6. Kyun? har bucket mein ab exactly ek loner plus complete pairs hain, to plain single-number trick har bucket par kaam karti hai.

Answer: 3 aur 6.

Verify: $3 \oplus 6 = 5$ jo step 1 se match karta hai, aur 3 mein divider bit set hai jabki 6 mein nahi — yeh alag buckets mein land karte hain jaise required. ✓

Cell D — `x & -x` on a positive integer

Worked example Example 4 — lowest set bit isolate karo

$x = 20$ . Compute $x & - x$ .

Forecast: $20 = 1010 0_{2}$ . Kaun sa power of two niklega — lowest ON bit ya highest?

Steps:

$20 = 1010 0_{2}$ likho. Lowest set bit position $2$ par hai (value $2^{2} = 4$ ); positions $0, 1$ zeros hain. Kyun? trick lowest 1 read karta hai, to pehle use locate karo.
Two's complement mein $- 20$ banao: $10100 \to 01011$ flip karo, $1$ add karo $\to 01100$ . Kyun? $- x = \neg x + 1$ ; "+1" trailing zeros ke through ripple karta hai aur exactly lowest 1 par rukta hai.
AND karo: $10100 & 01100 = 00100 = 4$ . Kyun? lowest bit ke upar dono operands complementary hain → sab zeros; position 2 par dono 1 hain → survive karta hai.

Answer: 4.

Verify: $20 = 4 \times 5$ aur $5$ odd hai, to $4 = 2^{2}$ sach mein $20$ ko divide karne wala largest power of two hai — yahi lowest set bit ki value hai. ✓

Cell E — `x & -x` on a NEGATIVE integer

Worked example Example 5 — LSB trick zero ke neeche bhi kaam karta hai

$x = - 12$ . $x & - x$ kya deta hai? (Yeh woh case hai jisse log darte hain — ek negative two's complement se phir se guzar raha hai.)

Forecast: kya answer sign par depend karta hai, ya sirf is par ki kaun se bits set hain? Guess karo.

Steps (clarity ke liye 8-bit words use karo):

$12 = 0000110 0_{2}$ . $- 12$ ka two's complement: flip $\to 11110011$ , add $1 \to 11110100$ . To $x = 1111010 0_{2}$ . Kyun? AND karne ke liye $- 12$ ka actual bit pattern chahiye.
Ab $- x = - (- 12) = 12 = 0000110 0_{2}$ . Kyun? negative ko negate karna positive deta hai; yahi x & -x ka doosra operand hai.
AND: $11110100 & 00001100 = 00000100 = 4$ . Kyun? sirf bit position 2 dono mein 1 hai → $x$ ka lowest set bit, bilkul positive inputs jaisa.

Answer: 4 — lowest set bit ki magnitude, sign-free.

Verify: $∣ - 12∣ = 12$ aur $12 & - 12$ bhi $4$ deta hai (same as Example 4 ka logic: $12 = 4 \times 3$ ). Trick bit pattern read karta hai, sign nahi. ✓

Cell F — zero aur degenerate inputs

Worked example Example 6 — woh corner cases jo koi test nahi karta

Har ek handle karo: (a) x & -x mein $x = 0$ ; (b) XOR loner trick mein single-element array [9]; (c) kya $16$ power of two hai?

Forecast: inme se kaun $0$ return karta hai, aur kaun "true" return karta hai?

Steps:

(a) $x = 0$ : $- 0 = 0$ , to $0 & 0 = 0$ . Kyun? koi set bit isolate karne ke liye hai hi nahi — flashlight kuch nahi dhundhta. Apna code guard karo: result par trust karne se pehle x != 0 check karo.
(b) [9]: accumulator $0 \oplus 9 = 9$ . Kyun? ek element, cancel karne ke liye koi pair nahi — single-number trick gracefully degenerate ho jaati hai "sirf wahi value return karo."
(c) $16 = 1000 0_{2}$ : test karo $16 & (16 - 1) = 10000 & 01111 = 0$ , aur $16 \neq = 0$ . Kyun? power of two mein exactly ek set bit hota hai, to use drop karne par $0$ milta hai. Logarithms and Powers of Two dekho.

Answers: (a) $0$ ; (b) $9$ ; (c) haan, $16$ power of two hai.

Verify: (a) koi bhi $x & - x$ tab $0$ hai jab $x = 0$ ; (b) ek-element list ka XOR woh element hi hai; (c) $lo g_{2} 16 = 4$ integer hai, jo single set bit confirm karta hai. ✓

Cell G — popcount: dense vs sparse loop counts

Worked example Example 7 — do tarike se set bits count karo, kaam compare karo

$x = 255$ (saare aath low bits on) aur $x = 64$ (ek bit on). Brian Kernighan ( $x & = x - 1$ ) har ek ke liye kitne loop iterations leta hai, naive shift loop ke comparison mein?

Forecast: sparse number 64 ke liye, kaun sa loop dramatically faster hai?

Steps:

$255 = 1111111 1_{2}$ → 8 set bits. Kernighan 8 baar loop karta hai (har set bit ke liye ek). Naive shift loop tab tak chalta hai jab tak $x$ $0$ na ho jaye = 8 shifts (bit length 8). Yahan dono tie karte hain. Kyun? har bit set hai, to "ek set bit kill karo" aur "ek bit ke upar shift karo" same cost lagata hai.
$64 = 100000 0_{2}$ → 1 set bit. Kernighan: $64 & 63 = 0$ ek step mein → count $= 1$ . Naive shift: $x$ ke $0$ tak pahunchne se pehle leading zeros cross karne ke liye 7 baar shift karna padega. Kyun? Kernighan zeros skip kar deta hai; woh sirf 1s par visit karta hai.

Answers: popcount $(255) = 8$ , popcount $(64) = 1$ . Kernighan iterations: $8$ aur $1$ . Naive iterations: $8$ aur $7$ .

Verify: $255 = 2^{8} - 1$ mein saare $8$ low bits set hain; $64 = 2^{6}$ mein exactly ek hai. Kernighan ki iteration count construction se popcount ke barabar hoti hai. ✓

Cell H — "thrice except one" twist (XOR YAHAN FAIL KARTA HAI)

Worked example Example 8 — ek ko chhodkar har element 3 baar aata hai

Array [5, 5, 5, 9]. XOR deta $5 \oplus 5 \oplus 5 \oplus 9 = 5 \oplus 9 = 12$ — galat, loner nahi hai. Sach wala single element dhundho.

Forecast: XOR pairs cancel karta hai, par triple ek copy chhodta hai. Kaun sa arithmetic triples cancel karta hai? Guess karo: kuch mod 3 wala.

Steps: har bit position ko mod 3 count karo; jahan loner mein 1 hai woh positions 3 ka multiple nahi honge.

Bits mein likho: $5 = 0101$ , $9 = 1001$ . Kyun? ab hum XOR karne ki jagah column by column tally karenge.
[5,5,5,9] mein column sums:
- bit 0: $1 + 1 + 1 + 1 = 4$ , $4 mod 3 = 1$ .
- bit 1: $0 + 0 + 0 + 0 = 0$ , $0 mod 3 = 0$ .
- bit 2: $1 + 1 + 1 + 0 = 3$ , $3 mod 3 = 0$ .
- bit 3: $0 + 0 + 0 + 1 = 1$ , $1 mod 3 = 1$ . Kyun? 5 ki teen copies har column mein 3 ke multiples contribute karti hain, mod 3 mein vanish ho jaati hain; sirf loner ke bits baahir dikhte hain.
mod-3 residues se reassemble karo: bits 3 aur 0 1 hain → $100 1_{2} = 9$ .

Answer: 9 (XOR akele ne galat 12 diya tha — yeh fix hai).

Verify: loner reconstructed $= 8 + 1 = 9$ , jo ek baar aane wale element se match karta hai. Memory trade-off ke liye Hash Sets vs O(1)-space tricks dekho. ✓

Cell I — ek real-world word problem

Worked example Example 9 — light-switch party

Ek room mein 5 lamps hain, sab OFF (state 00000). Guests apne number ke lamps toggle karte hain: guest events hain lamp 2, 4, 2, 5, 4, 4. XOR use karke on/off state track karo, end mein kaun se lamps ON hain?

Forecast: jo lamp even number of times toggle hua woh OFF wapas aa jaata hai; odd wala ON rehta hai. Kaun se lamps glow karte hain?

Steps (har lamp $k$ ko bit $2^{k - 1}$ se represent karo; toggle = woh bit state mein XOR karo):

Toggles tally karo: lamp 2 → do baar, lamp 4 → teen baar, lamp 5 → ek baar. Kyun? sirf parity matter karti hai (XOR self-inverse hai), to sirf even/odd counts chahiye.
Lamp 2: even → OFF. Lamp 4: odd → ON (bit $2^{3} = 8$ ). Lamp 5: odd → ON (bit $2^{4} = 16$ ). Kyun? $a \oplus a = 0$ even toggles erase karta hai; ek leftover single toggle bit set rakhta hai.
Final state $= 8 + 16 = 24 = 1100 0_{2}$ .

Answer: lamps 4 aur 5 ON hain; state $= 24$ .

Verify: toggle bits order mein XOR karo: start $0$ , $\oplus 2 = 2$ , $\oplus 8 = 10$ , $\oplus 2 = 8$ , $\oplus 16 = 24$ , $\oplus 8 = 16$ , $\oplus 8 = 24$ . Final $24 = 1100 0_{2}$ = lamps 4,5. ✓

Cell J — exam trap

Worked example Example 10 — negative par right-shift, aur aliased swap

(a) Signed 8-bit type mein, $- 8 >> 1$ kya hai? Kya yeh $- 4$ hai (division ki tarah)? (b) Tum XOR swap run karte ho a aur b par jahan dono ek hi variable ka naam hain jisme abhi 7 hai. Kya bachta hai?

Forecast: (a) kya arithmetic right-shift zero ki taraf round karta hai ya $- \infty$ ki taraf? (b) kya swap value preserve karta hai?

Steps:

(a) $- 8 = 1111100 0_{2}$ (two's complement, 8-bit). Arithmetic right-shift by 1 sign bit copy karta hai andar: $1111110 0_{2} = - 4$ . Kyun? yahan yeh $⌊ - 8/2 ⌋ = - 4$ ke barabar nikalta hai, par trap yeh hai ki rounding direction alag hai: e.g. $- 7 >> 1 = 1111110 0_{2} = - 4$ , jabki integer division $- 7/2$ toward $0$ truncate karta hai to $- 3$ . Shift $- \infty$ ki taraf round karta hai. Two's Complement Representation dekho.
(b) Aliased swap a^=b; b^=a; a^=b jab a aur b ek hi cell hain jisme 7 hai:
- a ^= b → cell ban jaata hai $7 \oplus 7 = 0$ .
- b ^= a → same cell $0 \oplus 0 = 0$ .
- a ^= b → $0 \oplus 0 = 0$ . Kyun? pehli line ne already shared cell zero kar diya; value 7 destroy ho gayi.

Answers: (a) $- 8 >> 1 = - 4$ , par $- 7 >> 1 = - 4 \neq = - 3$ — shifting negatives ke liye truncating division nahi hai. (b) aliased swap 0 chhodta hai, value obliterate ho jaati hai.

Verify: $(- 8) >> 1 = - 4$ aur $(- 7) >> 1 = - 4$ arithmetic shift ke under, jabki int(-7/2) toward zero $- 3$ hai; aur aliased XOR swap $0$ deta hai. ✓

Recall Har cell ka ek-line summary

Duplicate parity → XOR (cells A,B,I). Do loners → XOR phir differing bit par split (C). Lowest set bit → x & -x, sign-independent (D,E). $x = 0$ aur single elements guard karo (F). Sparse popcount → Kernighan (G). Triples → mod-3 bit tally, XOR galat hai (H). Negatives $- \infty$ ki taraf shift karte hain aur aliased swaps self-destruct karte hain (J).

Connections

Bit manipulation — XOR tricks, LSB, counting set bits (index 3.7.20) — parent topic.
Two's Complement Representation — Examples 5 aur 10.
Hash Sets vs O(1)-space tricks — Example 8 ka memory wala alternative.
Logarithms and Powers of Two — Example 6 mein power-of-two test.
Bitmask Dynamic Programming — subsets-as-integers, Example 9 ko extend karta hai.
Greedy and Divide-and-Conquer — Example 3 ka split-bit idea.