Bit manipulation — XOR tricks, LSB, counting set bits: Exercises

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

Level 1 — Recognition

Bas ek bit pattern padhna hai aur trick ka naam batana hai.

Exercise 1.1

$13$ ko 6-bit binary mein likho, aur har $1$ ki place value batao.

Recall Solution 1.1

Base-2 ka matlab hai $13$ ko powers of two ke sum ke roop mein likhna — parent note ki "switch row" se. $13 = 8 + 4 + 1 = 2^{3} + 2^{2} + 2^{0}$ 6 bits mein: $13 = 00110 1_{2}$ . $1$ s positions $3$ , $2$ , $0$ par hain, place values $8$ , $4$ , $1$ hain. Sabse rightmost $1$ (position $0$ , value $1$ ) LSB hai.

Exercise 1.2

6 ^ 6 aur 6 ^ 0 haath se compute karo. Ye kaun se laws hain?

Recall Solution 1.2

XOR ek bit ko $1$ tab set karta hai jab dono inputs alag hon.

6 ^ 6: har bit khud se compare hoti hai → kuch bhi alag nahi → $0$ . Yeh self-inverse law $a \oplus a = 0$ hai.
6 ^ 0: $6 = 11 0_{2}$ , XOR with $000$ → bits sirf wahan differ karti hain jahan $6$ mein $1$ hai → $11 0_{2} = 6$ . Yeh identity law $a \oplus 0 = a$ hai.

Exercise 1.3

$x = 20$ ke liye, x & -x aur x & (x-1) compute karo. Words mein batao ki har ek kya return karta hai.

Recall Solution 1.3

$20 = 1010 0_{2}$ .

x & -x sirf lowest set bit rakhta hai. $10100$ ka lowest $1$ position $2$ par hai, toh answer $0010 0_{2} = 4$ hai.
x & (x-1) lowest set bit drop karta hai. $x - 1 = 19 = 1001 1_{2}$ ; ANDing $10100 & 10011 = 1000 0_{2} = 16$ .

Level 2 — Application

Ab ek chote array ya number par ek trick apply karo.

Exercise 2.1

Array [7, 3, 5, 3, 7]. Ek ko chhod kar har value do baar aati hai. Use dhundho aur running XOR dikhao.

Recall Solution 2.1

Poori list ko XOR karo. Pairs self-destruct hote hain (even count → $0$ ); akela value (odd count) bacha rehta hai.

7 ^ 3 = 4
4 ^ 5 = 1
1 ^ 3 = 2 (yeh 3 pehle wale 3 ko cancel karta hai)
2 ^ 7 = 5 (yeh 7 pehle wale 7 ko cancel karta hai)

Answer: 5 — sirf wahi element jo odd number of times aata hai.

Exercise 2.2

Array [0, 1, 3, 4] mein $0..4$ ke sab numbers hone chahiye par ek missing hai. Sirf XOR se dhundho.

Recall Solution 2.2

Saare indices/values $0..4$ ko saare array elements ke saath XOR karo. Har present number apni copy ko full range mein cancel kar leta hai; absent number ke paas cancel karne wala koi nahi, toh woh reh jaata hai.

Full range: 0^1^2^3^4 = 4.
Array: 0^1^3^4 = 6.
Missing $= 4 \oplus 6 = 2$ .

Check: $0, 1, 3, 4$ present hain, toh 2 missing hai. ✓

Exercise 2.3

Kya $64$ ek power of two hai? x & (x-1) test use karo. Phir $48$ test karo.

Recall Solution 2.3

Power of two mein exactly ek set bit hoti hai; use drop karne se $0$ milta hai.

$64 = 100000 0_{2}$ . 64 & 63 = 1000000 & 0111111 = 0 → power of two ✓.
$48 = 11000 0_{2}$ . 48 & 47 = 110000 & 101111 = 100000 = 32 ≠ 0 → power of two nahi (iske do set bits hain).

Level 3 — Analysis

Kyun explain karo, ya koi edge case handle karo, sirf compute mat karo.

Exercise 3.1

$255$ ke set bits do tareekon se count karo: naive shift loop aur Brian Kernighan. Iteration counts compare karo.

Recall Solution 3.1

$255 = 1111111 1_{2}$ (aath $1$ s).

Naive (LSB padho, shift right): bit position har baar loop karta hai, yaani jab tak $x$ zero na ho jaye → 8 iterations.
Brian Kernighan (x &= x-1 ek set bit per loop khatam karta hai): set bit har baar loop karta hai → yahan bhi 8 iterations, kyunki saari bits set hain.

Insight: Kernighan sirf tab jeetta hai jab number sparse ho. Full number ke liye dono same kaam karte hain; count $= 8$ dono taraf.

Exercise 3.2

Prove karo ki x & -x highest nahi, lowest set bit isolate karta hai, $x = 12$ ke liye. Two's-complement steps dikhao.

Recall Solution 3.2

Maano $x = 12 = 110 0_{2}$ . Lowest set bit position $2$ par hai.

$\neg x = \dots 001 1_{2}$ (har bit flip karo).
$- x = \neg x + 1 = \dots 010 0_{2}$ (1 add karo; trailing $1$ s ripple kar $0$ ho jaate hain, pehla $0$ $1$ ban jaata hai).
x & -x = 1100 & 0100 = 0100 = 4 = 2^2.

Two's-complement +1 ek $1$ exactly lowest set position par land karta hai aur uske neeche $0$ s force karta hai; ANDing woh single bit rakhta hai aur upar sab cancel karta hai (high bits apne complements se milte hain). Ripple detail ke liye Two's Complement Representation dekho. Yeh provably hamesha LSB hota hai, kabhi MSB nahi.

Exercise 3.3

x = -8 (32-bit two's complement). Arithmetic shift mein x >> 1 kya hai, aur kyun yeh simply "2 se divide toward 0" nahi hai?

Recall Solution 3.3

$- 8$ two's complement mein ...11111000 hai. Arithmetic right shift sign bit ko top mein copy karta hai: $- 8 ≫ 1 = \dots 1111110 0_{2} = - 4.$ Yahan $- 8/2 = - 4$ exactly hai, toh theek lagta hai — lekin $- 9$ ke liye: $- 9 = \dots 110111, - 9 ≫ 1 = \dots 111011 = - 5,$ jabki $0$ ki taraf integer division $⌊ - 9/2 ⌋_{trunc} = - 4$ deta hai. Arithmetic shift $- \infty$ ki taraf round karta hai, $0$ ki taraf nahi. Yahi mismatch hai: shift $= ⌊ x / 2^{k} ⌋$ (floor) hai, jo negatives ke liye C-style truncation se alag hai.

Level 4 — Synthesis

Tricks combine karo ya unhe naye twist par adapt karo.

Exercise 4.1

Array [2, 5, 2, 7, 5, 9]: do numbers ek baar aate hain, baaki do baar. Dono dhundho. (Sab ka XOR unka XOR deta hai — unhe kaise alag karoge?)

Recall Solution 4.1

Sab kuch XOR karo: pairs cancel hote hain, $x \oplus y$ bach jaata hai jahan $x, y$ do singles hain.

2^5^2^7^5^9 = 7^9 = 14 = 1110_2.

$x \oplus y = 14 \neq = 0$ , toh $x, y$ kahin differ karte hain. $14$ ka koi bhi set bit lo — lowest pakdne ke liye d & -d use karo: 14 & -14 = 0010 = 2. Woh bit $x, y$ mein se exactly ek mein $1$ hai.

Array ko "kya bit- $1$ set hai?" ke hisaab se partition karo aur har group ko alag XOR karo (equal numbers same bit share karte hain toh pairs apne group mein cancel hote hain):

bit- $1$ set: $2, 2, 7$ → 2^2^7 = 7.
bit- $1$ clear: $5, 5, 9$ → 5^5^9 = 9.

Answer: 7 aur 9. ✓ (Neeche partition figure dekho.)

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

Exercise 4.2

Har element teen baar aata hai siwaaye ek ke (jo ek baar aata hai): [6, 6, 6, 4]. Yahan XOR kaam nahi karta — bit-count-mod-3 fix banao aur single dhundho.

Recall Solution 4.2

XOR pairs cancel karta hai (even counts), lekin teen copies ek copy chhod jaati hain — toh XOR yahan galat hai. Iske bajaye saare numbers mein har bit position count karo; tripled number ka bit $3$ ka multiple contribute karta hai, toh count % 3 single ke bits reveal karta hai.

$6 = 11 0_{2}$ , $4 = 10 0_{2}$ . Column sums:

bit $2$ (value $4$ ): $1 + 1 + 1 + 1 = 4$ , $4 mod 3 = 1$ → rakho.
bit $1$ (value $2$ ): $1 + 1 + 1 + 0 = 3$ , $3 mod 3 = 0$ → drop karo.
bit $0$ : sab $0$ → $0$ .

Reconstruct: bit $2$ set → $10 0_{2} = 4$ . Answer 4. ✓

Exercise 4.3

Subset ${0, 2, 3}$ of ${0, 1, 2, 3}$ ko ek bitmask integer ke roop mein represent karo. Phir element $1$ add karo aur element $2$ remove karo bit ops use karke. (Bitmask Dynamic Programming ke liye feed karta hai.)

Recall Solution 4.3

Ek subset ek mask hai jahan bit $i$ = "kya element $i$ present hai?"

${0, 2, 3} \to 110 1_{2} = 13$ (bits $0, 2, 3$ on).
Element $1$ add karo: OR se bit set karo → 13 | (1<<1) = 1101 | 0010 = 1111 = 15 → ${0, 1, 2, 3}$ .
Element $2$ remove karo: AND-NOT se bit clear karo → 15 & ~(1<<2) = 1111 & 1011 = 1011 = 11 → ${0, 1, 3}$ .

Final mask 11 $= {0, 1, 3}$ .

Level 5 — Mastery

Ek poore algorithm ke level par design ya reason karo.

Exercise 5.1

Diya hai $n$ (saare numbers $0.. n$ present hain siwaaye ek ke, array length $n$ ), tumhare paas pehle se XOR method hai. Alternative banao using count set bits reasoning, aur argue karo ki dono $O (n)$ , $O (1)$ space hain hash set ke muqable mein. Hash Sets vs O(1)-space tricks se jodo.

Recall Solution 5.1

XOR method (baseline): ans = (0^1^…^n) ^ (all elements), ek pass, ek accumulator → $O (n)$ time, $O (1)$ space.

Sum method (ek alternative "counting" flavour): poori range ka sum $S = \frac{n ( n + 1 )}{2}$ hai; actual array sum $A$ subtract karo. Tab missing = S - A. Yeh bhi $O (n) / O (1)$ hai, lekin bade $n$ ke liye overflow ho sakta hai, jabki XOR kabhi overflow nahi hota (result bit-width ke andar rehta hai). Woh robustness XOR ka advantage hai.

Hash set dekhi hui values store karta ( $O (n)$ extra memory) gap dhundhne ke liye — sahi hai par wasteful. In tricks ka poora point hash set ki memory ko ek single integer accumulator se trade karna hai: $O (1)$ space. XOR memory aur overflow-safety dono mein jeetta hai.

Exercise 5.2

Tumhe pata hai x = 0b0110100 = 52. Sirf x & -x ek loop mein use karke, saare set bits ki positions list karo (ek "bit iterator"). Har step dikhao.

Recall Solution 5.2

Baar baar lowest set bit pakdo, uski position record karo, phir use x &= x-1 se clear karo. Loop jab tak $x \neq = 0$ . $52 = 011010 0_{2}$ , set bits positions $2, 4, 5$ par.

x = 52 = 0110100. x&-x = 0000100 = 4 = 2^2 → position 2. x &= x-1 → 0110000 = 48.
x = 48 = 0110000. x&-x = 0010000 = 16 = 2^4 → position 4. x &= x-1 → 0100000 = 32.
x = 32 = 0100000. x&-x = 0100000 = 32 = 2^5 → position 5. x &= x-1 → 0. Ruko.

Positions: {2, 4, 5}. Iterations ki count = set bits ki count = $3$ (Brian Kernighan speed). ✓

Exercise 5.3 (Degenerate cases)

Har ek ke liye, output batao aur kyun: (a) 0 & -0, (b) 0 & (0-1), (c) $x = 0$ par power-of-two test, (d) empty array par XOR-single.

Recall Solution 5.3

Edge cases tricks ko honest rakhte hain — reader ko kabhi koi unseen scenario nahi milna chahiye.

(a) 0 & -0: $- 0 = 0$ , toh 0 & 0 = 0. Koi lowest set bit nahi hai, aur trick correctly $0$ return karta hai.
(b) 0 & (0-1) = 0 & -1 = 0 & (…1111) = 0. Kuch nahi se bit drop karna phir bhi kuch nahi hai.
(c) Power-of-two test x != 0 && (x & (x-1)) == 0: $x = 0$ ke liye pehla clause x != 0 false hai, toh $0$ correctly reject hota hai. (Us guard ke bina, 0 & -1 == 0 galat "haan" bolega.)
(d) XOR of an empty array = identity element $0$ (kuch accumulate karne ko nahi). $a \oplus 0 = a$ ke saath consistent hai.

Recall Feynman recap

Yahan har problem teen moves mein se ek thi disguise mein: XOR taaki duplicates gayab ho jaayein, x & -x taaki sabse neeche wale ON switch par flashlight point ho, aur x & (x-1) taaki woh light band ho jaye. Level 4 ne unhe mix kiya (distinguishing bit se split); Level 5 ne edges stress-test ki (zero, empty, overflow). Agar tum bata sako ki naye problem mein teen moves mein se kaunsa chahiye, toh topic master kar liya tumne.

Connections

Parent topic
Two's Complement Representation — woh ripple jo x & -x kaam karata hai.
Hash Sets vs O(1)-space tricks — Exercise 5.1 ka memory trade-off.
Bitmask Dynamic Programming — Exercise 4.3 ke subset masks.
Logarithms and Powers of Two — highest-bit vs lowest-bit.
Greedy and Divide-and-Conquer