Visual walkthrough — Bit manipulation — XOR tricks, LSB, counting set bits

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

Hum assume karte hain ki tum sirf yeh jaante ho: ek whole number ko ON/OFF switches ki ek row ke roop mein likha ja sakta hai. Yahi humara poora starting kit hai. Baaki sab kuch — minus sign, &, "lowest set bit" — yahan hum build karenge.

---

Step 1 — "Switches ki ek row" actually kya hoti hai

KYA. Ek non-negative integer switches ki ek row hoti hai. Right-to-left padhte hue, switch number $i$ ki value $2^i$ hai agar woh ON hai (ek $1$) aur kuch nahi agar woh OFF hai (ek $0$). Number un sabhi ON switches ka total hota hai.

$x={\sum }_{i=0}^{n-1}\underset{\begin{array}{c}\text{switch }i\\ \text{is }1\text{ or }0\end{array}}{\underbrace{b_i}}\cdot \underset{\begin{array}{c}\text{its worth}\\ \text{(place value)}\end{array}}{\underbrace{2^i}}$

Yahan $b_i$ switch $i$ ki state hai (ON $=1$, OFF $=0$), aur $2^i$ yeh batata hai ki woh switch kitna add karta hai agar woh ON ho. Har place value double hoti jaati hai jab tum left ki taraf badhte ho — yahi doubling ki wajah se base 2 kaam karta hai. (Dekhho Logarithms and Powers of Two ki kyun $2^i$ yahan natural ruler hai.)

YEH YAHAN SE KYU SHURU KAREIN. Is page ka har trick kaun se switches ON hain aur kahan hain ke baare mein hai. Isliye humein pehle "switch $i$" ko point karne aur uski price jaanne mein samarth hona chahiye.

PICTURE.

---

Step 2 — Kisi bhi number ki shape ko naam do

KYA. Koi bhi any $x\ne 0$ lo. $k$ ko uske sabse neeche ON switch ki position maano. Toh, "lowest" ki definition se, position $k$ se neeche har switch OFF hona chahiye. Isliye duniya ka har number aise dikhta hai:

$x=\underset{\begin{array}{c}\text{jo bhi upar}\\ \text{hai}\end{array}}{\underbrace{a}}\underset{\begin{array}{c}\text{position }k\\ \text{lowest ON}\end{array}}{\underbrace{1}}\underset{\begin{array}{c}k\text{ zeros}\\ \text{neeche}\end{array}}{\underbrace{00\cdots 0}}$

• $a$ = "high part" — position $k$ ke upar ke switches. Hum nahi care karte ki woh kya hain; woh kuch bhi ho sakte hain.
• Akela $1$ = sabse neeche ON switch, position $k$ par baitha.
• $k$ trailing zeros = neeche sab kuch, guaranteed OFF kyunki $k$ sabse neeche ON switch tha.

KYU. Hum ek aisa proof chahte hain jo har number ke liye kaam kare, isliye ek example ki jagah hum woh general skeleton describe karte hain jo har number share karta hai. Agar hum yeh dikha sakein ki trick is skeleton par kaam karti hai, toh yeh har jagah kaam karti hai.

PICTURE.

---

Step 3 — Minus sign switches ki row ke saath kya karta hai

KYA. -x karne ke liye ek computer two's complement use karta hai: har switch ko flip karo, phir $1$ add karo.

$-x=\underset{\text{flip all switches}}{\underbrace{(\neg x)}}+1$

$\neg$ ("NOT") har ON ko OFF aur har OFF ko ON kar deta hai. Phir hum seedha $1$ add karte hain.

KYU ordinary subtraction ki jagah yeh tool. Hum "kya hai $0-x$?" slow tarike se pooch sakte the, lekin woh kahan switches land karte hain chhupa deta hai. Two's complement woh definition hai jo hardware actually use karta hai (dekhho Two's Complement Representation), aur — crucially — yeh ek hi description hai jo humein har switch ki final state predict karne deti hai. AND result prove karne ke liye humein switch-level prediction chahiye, isliye yeh sahi lens hai.

PICTURE.

---

Step 4 — Skeleton ko flip karo ($-x$ banane ka step 1)

KYA. Step 2 ke skeleton par $\neg$ apply karo. Flipping $a\to \bar{a}$ karta hai, akela $1\to 0$ ho jaata hai, aur trailing $0\cdots 0\to 1\cdots 1$ ho jaata hai:

$\neg x=\underset{\begin{array}{c}\text{high bits,}\\ \text{sab flip hue}\end{array}}{\underbrace{\bar{a}}}\underset{\begin{array}{c}\text{position }k\\ \text{par 1 tha}\end{array}}{\underbrace{0}}\underset{\begin{array}{c}k\text{ ones}\\ \text{(zeros the)}\end{array}}{\underbrace{11\cdots 1}}$

• $\bar{a}$ = high part jisme har switch flip ho gaya.
• Position $k$ par $0$ = humara sabse neeche ON switch, ab OFF ho gaya.
• $k$ trailing $1$s = guaranteed zeros, ab sab ON ho gaye.

KYU. Yeh literally two's-complement recipe ka pehla adha hai. Hum ise alag karte hain taaki agla step ($1$ add karna) ek saaf starting picture se shuru ho.

PICTURE.

---

Step 5 — 1 add karo aur carry ko ripple karte dekho

KYA. Ab $\neg x$ mein $1$ add karo. $1$ add karna sabse rightmost switch ko hit karta hai. Lekin woh switch $1$ hai, isliye woh $0$ mein flip hota hai aur carry left ki taraf jaata hai. Agla switch bhi $1$ hai → $0$ mein flip hota hai, phir carry aata hai. Yeh ripple poore $k$ trailing ones ke block mein daudta hai aur finally position $k$ par rukta hai, jo $0$ tha: woh $1$ ban jaata hai aur carry khatam ho jaata hai.

$-x=\underset{\begin{array}{c}\text{carry ne nahi}\\ \text{chhhua}\end{array}}{\underbrace{\bar{a}}}\underset{\begin{array}{c}\text{position }k\\ \text{carry yahan ruka}\end{array}}{\underbrace{1}}\underset{\begin{array}{c}k\text{ zeros}\\ \text{(carry ne clear kiya)}\end{array}}{\underbrace{00\cdots 0}}$

• $\bar{a}$ = high part, unchanged — carry kabhi wahan nahi pahuncha.
• Position $k$ par $1$ = carry finally pehle $0$ par utara jo mile aur use ON kar diya.
• $k$ trailing $0$s = ripple ne un sabhi $1$s ko wapas $0$ mein flip kar diya.

KYU. Yeh carry ripple hi pura raaz hai. Notice karo payoff: position $k$ par, dono $x$ (Step 2) aur $-x$ mein $1$ hai. $k$ se neeche har jagah, dono $0$ hain. Yeh alignment wahi hai jo agla step cash karta hai.

PICTURE.

---

Step 6 — Unhe AND karo, switch by switch

KYA. & (AND) ek switch ko ON tabhi rakhta hai jab woh dono numbers mein ON ho. $x$ ko $-x$ ke upar line up karo aur har column compare karo.

region	$x$	$-x$	AND result	reason
high bits	$a$	$\bar{a}$	$0$	$a$ aur uska flip $\bar{a}$ kabhi dono ON nahi
position $k$	$1$	$1$	$1$	dono ON → bachta hai
$k$ se neeche	$0$	$0$	$0$	dono OFF

High part isliye khatam ho jaata hai kyunki ek switch aur uska apna flip kabhi dono ON nahi ho sakte — yahi $\bar{a}$ ka matlab hai. Trailing part isliye khatam ho jaata hai kyunki dono OFF hain. Sirf position $k$ bachti hai.

$\boxed{x\&(-x)=2^k}$

• $x\&(-x)$ = number aur uske negative ka AND.
• $2^k$ = position $k$ par ek akela ON switch — precisely lowest set bit, isolate aur saaf.

KYU. Yeh Step 1 ka goal hai, ab general skeleton ke liye prove ho gaya — isliye yeh har number ke liye hold karta hai.

PICTURE.

---

Step 7 — Degenerate case: $x=0$

KYA. Kya hoga agar koi bhi switch ON na ho? Toh $x=0$, aur $-0=0$ bhi (sabhi switches flip karo → sab $1$s; $1$ add karo → carry ripple end se nikal jaata hai → sab wapas $0$s). $0$ aur $0$ ka AND $0$ hai.

$0\&(-0)=0$

KYU MATTER KARTA HAI. Jab kuch ON nahi hota toh koi "lowest set bit" nahi hota, isliye trick correctly $0$ return karti hai — "koi bit nahi mila" ka honest jawaab. Agar code mein real bit expected hai toh hamesha isse guard karo. Har doosra input ($x\ne 0$) mein kam se kam ek ON switch hota hai, isliye Steps 2–6 unchanged apply hote hain. Koi aur case nahi hain: ek number ya toh all-off hai ($x=0$) ya uska ek well-defined lowest ON switch hai.

PICTURE.

---

Ek-picture summary

Ek hi canvas par poori derivation: skeleton $a10\cdots 0$, uska negative $\bar{a}10\cdots 0$ jo flip-then-carry se bana, aur AND jo sirf position $k$ par bachta hai.

Recall Feynman retelling — seedhe shabdon mein poora walkthrough

Ek number light switches ki ek row hai. Sabse neeche woh switch dhundho jo jal raha ho — uski jagah ko $k$ kaho. Usse neeche sab andhera hai (yahi "lowest" ka matlab hai).

Ab negative banao: har switch flip karo (lights darks se swap ho jaati hain), phir ek add karo. Ek add karna sabse far-right switch ko hit karta hai. Kyunki flipping ne un sab neeche ke switches ko ON kar diya tha, "+1" unhe ek ek karke band kar deta hai, ek chhoti si wave left ki taraf roll karti hai, jab tak woh pehle OFF switch tak nahi pahunch jaati — jo exactly spot $k$ par hai. Wahan wave rukti hai aur us switch ko ON kar deti hai.

Toh ab dono rows dekho: original ka sabse neeche light spot $k$ par hai; negative ka bhi spot $k$ par light hai; aur $k$ se neeche dono andhere hain. $k$ se upar har jagah, negative original ka exact opposite hai, isliye kisi column mein dono jale nahi hain.

AND ka matlab hai "light tabhi rakho jab DONO rows mein ho." Ek hi jagah dono jale hain woh spot $k$ hai. Toh AND sab kuch mita deta hai sirf us ek light ko chhodkar: tum ek akeli glow ke saath bachte ho lowest set bit par — number $2^k$. Aur agar number shuru se hi andhera tha ($0$), toh uska negative bhi andhera hai, aur kuch nahi bachta — tumhe $0$ milta hai, jo sahi "koi bit nahi" answer hai.

Connections

• Two's Complement Representation — woh flip-and-add-one jo Step 5 ka ripple possible karta hai.
• Hash Sets vs O(1)-space tricks — yeh bit scale par O(1)-space philosophy hai.
• Bitmask Dynamic Programming — x & -x ek subset ke members ko ek bit at a time iterate karta hai.
• Logarithms and Powers of Two — $2^k$ place-value ruler aur highest-bit contrast.
• Greedy and Divide-and-Conquer (Algorithm Paradigms)