બીટ-હેરાફેરીના સામાન્ય યુક્તિ શું છે?

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 ઘણી સંયોજક સ્થિતિ-જગ્યા સમસ્યાઓને આકર્ષક બનાવે છે. તે સિસ્ટમ્સ, ગ્રાફિક્સ, સંકોચન અને કર્મક્ષમતા-જટિલ કોડમાં આવશ્યક છે જ્યાં દરેક ચક્ર ગણતરી કરે છે.