Bit manipulation — XOR tricks, LSB, counting set bits: Question bank

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

Sach ya jhooth — justify karo

Har statement ya toh sach hai ya jhooth. Reveal mein wajah di gayi hai, jo asli important part hai.

a ^ a == 0 har integer a ke liye, negatives aur zero sameit.

Sach. XOR poochta hai "kya bits alag hain?" — ek value kabhi khud se alag nahi hoti, isliye har bit test false hota hai aur result all-zero hota hai, sign ya magnitude chahe kuch bhi ho.

a ^ 0 == a hamesha.

Sach. Zero mein koi 1-bit nahi hai, isliye koi bhi bit position "differ" nahi karta jahan a 0 ho, aur jahan a 1 ho wahan 0 differ karta hai, 1 ko keep karte hue. Kuch nahi badalti — yeh identity law hai.

Ek list ko XOR karne par woh element milta hai jo odd number of times appear karta hai.

Sach. Har value jo even number of times XOR hoti hai woh cancel ho ke 0 ban jaati hai (self-inverse), isliye sirf odd count wali values bachti hain; agar exactly ek odd hai, toh wahi bachta hai.

x & -x x ka highest set bit return karta hai.

Jhooth. Yeh lowest set bit return karta hai. Two's complement (-x = ~x + 1) trailing zeros ko zeros rakhta hai aur exactly lowest set position par 1 lagata hai, isliye AND sirf wahin bachta hai.

x & (x - 1) == 0 matlab x power of two hai.

Almost — iska matlab hai x power of two hai ya x == 0. Ek-bit number ka lowest set bit drop karne par 0 milta hai; lekin 0 mein koi set bit nahi hai aur woh bhi pass ho jaata hai, isliye x != 0 ka guard zaroori hai.

Kisi bhi x ke liye, x << k equals x * 2**k.

Sirf mathematical value ke liye sach hai jab tak koi bit integer width se overflow na kare. Fixed-width types mein high bits gir jaate hain, isliye arithmetic identity tabhi hold karti hai jab x * 2**k fit ho.

x >> k equals floor(x / 2**k) sab integers x ke liye.

Sach agar aap floor toward

- \infty

accept karo. Negative x ke liye arithmetic shift ke saath, jaise -1 >> 1 == -1, yeh floor division hai, woh "round toward zero" nahi jo kai languages mein / deta hai.

XOR associative hai, isliye array fold karne ka order result nahi badalta.

Sach. Har bit position independently compute hoti hai aur single bit par XOR associative aur commutative hai, isliye koi bhi grouping ya ordering same final bits deti hai.

Brian Kernighan ka x &= x - 1 loop word mein har bit ke liye ek baar run karta hai.

Jhooth. Yeh har set bit ke liye ek baar run karta hai, kyunki har iteration exactly ek 1 clear karta hai. Sparse number ke liye yeh word width se kaafi kam hota hai.

XOR-swap trick kisi bhi do variables ke liye kaam karta hai.

Jhooth. Yeh tab fail hota hai jab dono names same storage ko refer karein: a ^= a use zero kar deta hai, toh dono 0 ho jaate hain. Yeh sirf distinct locations ke liye kaam karta hai.

~x == -x - 1 two's complement mein.

Sach. Definition se -x = ~x + 1, toh rearrange karne par ~x = -x - 1 milta hai. NOT ko sanity-check karne ke liye yeh ek handy identity hai.

Error dhundho

Har snippet ya claim mein ek bug ya galat step hai. Reveal se pehle bolo kya galat hai.

"Array mein 0..n ka missing number dhundne ke liye, sirf array elements ko XOR karo."

Galat — yeh sirf array ke andar ke duplicates cancel karta hai. Tumhe har index 0..n bhi XOR karna hoga; tab har present number apni value cancel karta hai aur absent wala bach jaata hai.

"single finder: array ko XOR karo, kaam karta hai jab baaki har element teen baar appear kare."

Galat. XOR pairs mein cancel karta hai (even counts). Teen copies ek copy uncancelled chhodti hain, answer corrupt ho jaata hai. "Sab teen baar except ek" ke liye tumhe per-bit counting mod 3 chahiye.

"Power of two check karo (x & (x-1)) == 0 se."

Incomplete — x == 0 case miss ho gayi, jo 0 return karta hai lekin power of two nahi hai. Correct guard: x != 0 && (x & (x-1)) == 0.

"count += x & 1; x >>= 1 ek while(x) loop mein kisi bhi int ke set bits safely count karta hai."

Negatives ke liye dangerous: arithmetic right shift ke saath sign bit refill hoti rehti hai, toh while(x) kabhi terminate nahi ho sakta. Unsigned type ya fixed bit-count loop use karo.

"Lowest set bit isolate karne ke liye, x & (x - 1) use karo."

Yeh toh ulta karta hai — yeh lowest set bit clear karta hai. Use isolate karne ke liye x & -x chahiye.

"XOR swap temporary variable se faster hai, isliye ise prefer karo."

Modern CPUs par yeh faster nahi hai (yeh data dependency chain banata hai aur register renaming block karta hai) aur aliasing par fail hota hai. Temp wala version clearer hai aur kam se kam utna hi fast.

"x & -x se 2**k milta hai, toh iska log2 lena hamesha cleanly integer index deta hai."

Index integer hai, lekin ise floating-point log2 se compute karne par large k ke liye rounding error ka risk hai. Integer trailing-zero counts prefer karo. Dekho Logarithms and Powers of Two.

Why questions

Yeh mechanism probe karte hain. Sirf tab reveal karo jab tum explain kar sako.

XOR karne par duplicates zero mein kyun cancel ho jaate hain?

Self-inverse law a ^ a = 0 ki wajah se: do identical values har bit mein agree karti hain, isliye har "kya woh differ karte hain?" test false hota hai, aur result all zeros hota hai.

Two's complement x & -x ko specifically lowest set bit par kyun land karta hai?

x ko flip karne par trailing zeros ones ban jaate hain; 1 add karne par ripple up hoti hai aur pehle 0 par (purana lowest set bit) ruk jaati hai, wahan 1 place karte hue. Us position ke upar flipped bits original ke complement hain, isliye AND unhe cancel kar deta hai.

Brian Kernighan ka popcount sparse numbers ke liye kyun preferred hai?

Yeh bit width ki jagah har set bit ke liye ek baar loop karta hai, isliye kam 1s wala number few iterations mein khatam hota hai chahe word kitni bhi wide ho.

x & (x - 1) exactly lowest set bit clear karta hai aur kuch nahi, kyun?

1 subtract karne par lowest 1 flip ho ke 0 ban jaata hai aur uske neeche ke sab zeros 1s ban jaate hain; original se AND karne par woh poora low block wipe ho jaata hai, jabke lowest 1 ke upar har bit unchanged rehti hai aur survive karti hai.

XOR missing number hash set ke unlike no extra memory use karke kyun dhoondh sakta hai?

XOR sab information ek single running accumulator mein cancellation use karke fold karta hai, isliye

O (1)

space chahiye. Ek hash set lookup ke liye har element store karta hai,

O (n)

space costing — yeh trade-off Hash Sets vs O(1)-space tricks mein explore ki gayi hai.

Left shift power of two se multiply kyun karta hai?

Har bit ko ek position upar shift karne par har bit ki place value

2^{i}

2 se multiply hoti hai, aur poora base-2 sum 2 se multiply karna 2 se multiplication hai —

k

baar repeat karne par

\times 2^{k}

milta hai.

x & -x trick par trust karne ke liye two's complement kyun samajhna zaroori hai?

Kyunki yeh trick poori tarah is baat par depend karti hai ki -x kaise represent hota hai; "flip and add 1" definition ke bina, koi reason nahi hai ki AND low bit isolate kare. Yeh link hai Two's Complement Representation se.

Edge cases

Woh scenarios jinhe log bhool jaate hain. Reveal se pehle output predict karo.

x & -x kya deta hai jab x == 0 ho?

Yeh 0 deta hai. Koi set bit nahi hai isolate karne ke liye, aur -0 == 0, isliye 0 & 0 == 0. Koi bhi code jo nonzero result assume kare use zero special-case karna hoga.

XOR "single number" fold khaali array ke liye kya return karta hai?

Yeh 0 return karta hai, identity element, kyunki koi value fold na karne par accumulator apne starting 0 par hi rehta hai — meaningful sirf tab agar tum "no unique element" ko 0 maano.

Ek number jiske sab bits 1 hain uska popcount kya hota hai (jaise all-ones word)?

Yeh bit width ke barabar hota hai (har switch on). Brian Kernighan ka loop tab full width times run karta hai — uska worst case, naive loop se match karte hue.

x & (x - 1) ke saath kya hota hai jab x == 0 ho?

0 - 1 all-ones hai (two's complement mein -1), aur 0 & (all ones) == 0. Toh result 0 hai aur koi bhi while(x) loop simply execute nahi hoga — safe hai lekin reminder hai ki 0 mein drop karne ke liye koi bit nahi hai.

XOR-swap kya karta hai jab dono variables mein already equal values hon?

Agar woh distinct locations hain dono v hold karte hue, toh phir bhi kaam karta hai: v ^ v = 0, phir reveals har ek mein v restore karte hain. Sirf aliasing (same location) use break karta hai, equal values nahi.

Missing-number XOR trick ke liye, kya hoga agar koi number missing na ho (array poora 0..n ho)?

Har value apna index cancel kar deti hai, 0 bachta hai. Toh 0 result ko carefully interpret karna hoga — iska matlab ho sakta hai "0 missing hai" ya "kuch missing nahi hai," yeh tumhare index range convention par depend karta hai.

Ek negative number ko uski full width se right-shift karne par kya milta hai?

Arithmetic shift ke saath yeh sab sign bits mein collapse ho jaata hai: -5 >> 31 (32-bit) -1 hai, 0 nahi, kyunki sign bit fill hoti rehti hai. Isliye pure bit work mein unsigned types use karni chahiye.

Connections

Parent topic
Two's Complement Representation — kyun -x low bit isolate karta hai.
Hash Sets vs O(1)-space tricks — XOR ke peeche memory trade-off.
Bitmask Dynamic Programming — integers as subsets.
Logarithms and Powers of Two — powers se bit index.
Greedy and Divide-and-Conquer