बिट मॅनिपुलेशनच्या सामान्य ट्रिक्स कोणत्या आहेत?

Question

Accepted Answer

**Bit manipulation** AND, OR, XOR, NOT आणि shifts वापरून पूर्णांकांच्या बायनरी प्रतिनिधित्वावर थेट कार्य करते. हे कॉम्पॅक्ट, शाखा-मुक्त आणि अत्यंत वेगवान ऑपरेशन्स सक्षम करते. ## मुख्य ऑपरेशन्स ```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 ``` ## उपयोगी ट्रिक्स ```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) ``` ## उदाहरण: एकल संख्या शोधा (XOR ट्रिक) ```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 ``` ## जटिलता Bit ops O(1) आहे; वरील XOR स्कॅन **O(n) वेळ, O(1) जागा** आहे. ## कधी वापरावे / नुकसान **bitmasks** (subset enumeration, states वर DP), flags, वेगवान गणित आणि कमी-स्तरीय/embedded कोडसाठी वापरा. चिन्ह बिट्स, भाषा-विशिष्ट shift वर्तन आणि वाचनीयतेसाठी सावधान रहा — अस्पष्ट ट्रिक्स कमेंट करा. ## हे महत्वाचे का आहे Bit manipulation ने O(1)-स्पेस सलव्हीज तयार केल्या (XOR single-number trick सारख्या) जे मुलाखतीत आश्चर्यकारक आहेत. Bitmask DP बर्‍याच संयोजक स्टेट-स्पेस समस्या सुवाह्य करते. हे सिस्टम्स, ग्राफिक्स, कॉम्प्रेशन आणि कार्यक्षमता-गंभीर कोडमध्ये अत्यावश्यक आहे जेथे प्रत्येक सायकल महत्वाचा आहे.