बिट-हेराफेरी की सामान्य ट्रिकें क्या हैं?

Question

Accepted Answer

**बिट हेराफेरी** AND, OR, XOR, NOT और शिफ्ट्स का उपयोग करके पूर्णांकों के बाइनरी प्रतिनिधित्व पर सीधे काम करती है। यह कॉम्पैक्ट, शाखा-मुक्त और बहुत तेज़ संचालन सक्षम करती है। ## मुख्य संचालन ```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 ``` ## जटिलता बिट ऑप्स O(1) हैं; ऊपर दिया गया XOR स्कैन **O(n) समय, O(1) स्पेस** है। ## कब उपयोग करें / खतरे **बिटमास्क** (सबसेट गणना, स्थितियों पर DP), फ्लैग, तेज़ गणित और निम्न-स्तर/एम्बेडेड कोड के लिए उपयोग करें। साइन बिट्स, भाषा-विशिष्ट शिफ्ट व्यवहार और पठनीयता से सावधान रहें — गैर-स्पष्ट ट्रिक्स पर टिप्पणी करें। ## यह क्यों महत्वपूर्ण है बिट हेराफेरी सुंदर O(1)-स्पेस समाधान प्रदान करती है (जैसे XOR एकल-संख्या ट्रिक) जो साक्षात्कार में आश्चर्यजनक हैं। बिटमास्क DP कई संयोजी राज्य-स्पेस समस्याओं को सुलभ बनाता है। यह सिस्टम, ग्राफिक्स, संपीड़न और प्रदर्शन-महत्वपूर्ण कोड में आवश्यक है जहां हर चक्र महत्वपूर्ण है।