Yaygın bit manipülasyonu hileleri nelerdir?

Question

Accepted Answer

**Bit manipülasyonu** AND, OR, XOR, NOT ve kaydırmaları kullanarak tamsayıların ikili gösterimine doğrudan işlem yapar. Kompakt, dallanmasız ve çok hızlı işlemleri sağlar. ## Temel işlemler ```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 ``` ## Yararlı hileler ```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) ``` ## Örnek: tek sayıyı bul (XOR hileleri) ```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 ``` ## Karmaşıklık Bit işlemleri O(1); yukarıdaki XOR taraması **O(n) zaman, O(1) alan**. ## Kullanıldığı zaman / tuzaklar **Bitmasklar** (alt küme numaralandırması, durumlar üzerinde DP), bayraklar, hızlı matematik ve düşük seviye/gömülü kod için kullanın. İşaret bitleri, dile özgü kaydırma davranışı ve okunabilirlik konusunda dikkat edin — açık olmayan hileleri açıklayın. ## Neden önemli Bit manipülasyonu, görüşmelerde hayrete düşüren O(1)-alan çözümleri sağlar (XOR tek sayı hileleri gibi). Bitmask DP birçok kombinatorik durum-uzay problemini çözülebilir hale getirir. Sistemler, grafik, sıkıştırma ve her döngünün önemli olduğu performans açısından kritik kodda gereklidir.