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

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

Yeh page kuch bhi assume nahi karta. Hum har symbol build karte hain jis par parent note Bit Manipulation rely karta hai, ek aisi order mein jahan har idea use hone se pehle earn kiya jaata hai.

1. Ek bit — single switch

Socho ek light switch wall par. Neeche = 0, upar = 1. Yeh ek bit hai. Hum inhe squares ki tarah draw karenge: ek filled square 1 hai, ek empty square 0 hai.

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

Topic ko yeh kyun chahiye: parent note ki har trick individual switches ko manipulate karti hai. Agar aap sochte raho "13 ek number hai", toh tricks riddles jaisi lagti hain. Agar aap socho "13 switches ka ek specific pattern hai", toh woh visible ho jaati hain.

2. Place value aur base-2 sum $x = \sum b_{i} 2^{i}$

Ek switch sirf ON ya OFF hold karta hai. Bade numbers store karne ke liye hum kai switches line up karte hain, aur — jaise ordinary numbers mein tens/hundreds columns hote hain — har position apne daayein wale se zyada worth hoti hai.

Symbols ek ek karke padhte hain:

$b_{i}$ (padho "bee-sub-eye") position $i$ par switch ki value hai. Yeh $0$ ya $1$ hai.
$2^{i}$ place value hai: $2^{0} = 1, 2^{1} = 2, 2^{2} = 4, 2^{3} = 8, \dots$
$\sum_{i = 0}^{n - 1}$ (bada Greek $Σ$ , "sigma") bas matlab hai add up karo terms ko jab $i$ , $0$ se $n - 1$ tak chalta hai. Yeh " $+$ everything" ka shorthand hai.

Inhe saath rakhke:

$x = \sum_{i = 0}^{n - 1} b_{i} 2^{i} = b_{0} \cdot 1 + b_{1} \cdot 2 + b_{2} \cdot 4 + b_{3} \cdot 8 + \dots$

Har switch ya toh apni place value contribute karta hai (agar $b_{i} = 1$ ) ya kuch nahi (agar $b_{i} = 0$ ).

Topic ko yeh kyun chahiye: parent ki bilkul pehli formula yahi sum hai, aur "power of two" (jo x & (x-1) test mein use hota hai) ka matlab hai exactly ek switch ON hai — aap yeh place value ke bina nahi dekh sakte. Reverse question ke liye ("kaunsi position?") dekho Logarithms and Powers of Two.

3. Least Significant Bit (LSB)

Iska opposite hai Most Significant Bit (sabse baayein), jo sabse zyada worth hota hai.

LSB position ::: position 0, sabse daayein wala bit LSB place value ::: $2^0 = 1$

4. Chhe operators — har ek switches ke saath kya karta hai

Neeche har operator switches par kaam karta hai, position by position, independently. Inhe ek ek karke padho.

Truth tables (ek input bit column har ek, daayein par output):

a 0011 b 0101 a & b 0001 a ∣ b 0111 a \oplus b 0110

Yahan $\oplus$ bas XOR ka math symbol hai (code mein ^). Iska column dekho: ON tabhi jab dono inputs alag hon. Yeh single fact parent ke section 2 ka poora engine hai.

Shifts multiply/divide kyun hain

Har switch ko ek place baayein slide karna har place value double kar deta hai ( $2^{i} \to 2^{i + 1}$ ), toh number double ho jaata hai:

$x ≪ k = x \cdot 2^{k}, x ≫ k = ⌊ \frac{x}{2 ^{k}} ⌋$

Symbol $⌊ ⌋$ (floor brackets) ka matlab hai "poore number tak neeche round karo" — kyunki right shift se daayein edge se girne wale bits drop ho jaate hain, koi remainder throw away ho jaata hai.

Topic ko yeh chhhon kyun chahiye: parent note ki code ki literally har line inhi operators se bani hai aur kuch nahi.

5. Negative numbers: two's complement aur $- x$

Parent ki x & -x trick $- x$ use karti hai. Lekin switches ki row mein $- x$ hota kya hai? Computer ke paas koi "minus sign switch" nahi hota; woh negatives ko two's complement namak rule se encode karta hai.

Yeh rule kyun? Kyunki yeh $x + (- x) = 0$ ko automatically sahi banata hai jab aap switches ko carry ke saath add karte ho, toh CPU plus aur minus dono ke liye same adder use kar sakta hai. (Poori kahani Two's Complement Representation mein.)

Topic ko yeh kyun chahiye: two's complement ke bina, parent mein boxed result $x & - x = 2^{k}$ explain nahi ho sakta. Two's complement woh hidden gear hai jo LSB trick ko chalata hai.

6. Counting: "kitne switches ON hain?" (popcount)

Koi naya symbol nahi — bas ek count ka naam. Lekin iska apna word deserve karta hai kyunki parent ka ek poora section isse fast compute karne ke liye dedicated hai.

popcount of 1101 ::: 3 (teen ON switches) popcount of 0 ::: 0

Topic ko yeh kyun chahiye: "power of two" test, Brian Kernighan ka loop, aur bahut saare interview problems ON switches count karne par reduce hote hain.

7. Pieces topic ko kaise feed karte hain

Upar se neeche padho: switches → place value → number; wahan se hum teen superpowers mein branch karte hain, aur notice karo two's complement operators aur LSB trick ke beech mein baitha hai — yeh woh bridge hai jise aapko cross karna hai.

Equipment checklist

Daayein side cover karo aur oonchi awaaz mein jawab do. Agar koi line rokti hai, parent note se pehle uska section dobara padho.

Bit kya hai, plain words mein?

Ek switch, ya toh OFF (0) ya ON (1).

Position

i

par switch ki place value kya hai?

2^{i}

(toh positions worth hain

1, 2, 4, 8, \dots

\sum_{i = 0}^{n - 1} b_{i} 2^{i}

kya compute karta hai?

Number ki value: har place value

2^{i}

add karo jiska switch

b_{i}

ON hai.

Kaunsa switch LSB hai aur woh kitna worth hai?

Sabse daayein wala, position 0, worth

2^{0} = 1

a & b kisi position par ON kab hota hai?

Sirf jab dono inputs wahan ON hon.

a ^ b (XOR) kisi position par ON kab hota hai?

Sirf jab dono inputs alag hon.

~x (NOT) kya karta hai?

Har switch flip karta hai.

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

x \cdot 2^{k}

aur

⌊ x / 2^{k} ⌋

Switches se

- x

kaise banate hain?

Har bit flip karo, phir 1 add karo (two's complement).

"Popcount" ka matlab kya hai?

Kitne switches ON hain (set bits).

Switches mein power of two special kyun hai?

Exactly ek switch ON hota hai.