بٹ مینیپولیشن کی عام ترکیبیں کیا ہیں؟

Question

Accepted Answer

**Bit manipulation** براہ راست integers کی binary نمائندگی پر AND، OR، XOR، NOT، اور shifts استعمال کرتے ہوئے کام کرتا ہے۔ یہ compact، branch-free، اور بہت تیز operations فراہم کرتا ہے۔ ## Core operations ```python x & 1 # is x odd? (lowest bit) x << 1 # multiply by 2 x >> 1 # integer divide by 2 x & (1 << k) # is bit k set? x | (1 << k) # set bit k x & ~(1 << k) # clear bit k x ^ (1 << k) # toggle bit k ``` ## Useful tricks ```python x & (x - 1) # clears the lowest set bit x & (x - 1) == 0 # is x a power of two? (x>0) x & (-x) # isolates the lowest set bit bin(x).count('1') # popcount (number of set bits) ``` ## مثال: single number تلاش کریں (XOR trick) ```python def single_number(nums): result = 0 for n in nums: result ^= n # pairs cancel: a ^ a == 0 return result # the lone unpaired value remains single_number([4, 1, 2, 1, 2]) # -> 4 ``` ## Complexity Bit ops O(1) ہیں؛ اوپر دیا گیا XOR scan **O(n) time، O(1) space** ہے۔ ## کب استعمال کریں / خطرات **Bitmasks** (subset enumeration، DP over states)، flags، fast math، اور low-level/embedded code کے لیے استعمال کریں۔ Sign bits، language-specific shift behavior، اور readability سے احتیاط رکھیں — غیر واضح tricks پر comment کریں۔ ## یہ کیوں اہم ہے Bit manipulation elegant O(1)-space solutions فراہم کرتا ہے (جیسے XOR single-number trick) جو interviews میں حیران کن ہوتے ہیں۔ Bitmask DP بہت سے combinatorial state-space مسائل کو قابل عمل بناتا ہے۔ یہ systems، graphics، compression، اور performance-critical code میں ضروری ہے جہاں ہر cycle اہم ہے۔