ビット操作の一般的なトリックは何ですか?

Question

Accepted Answer

**Bit manipulation** は 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) 空間** です。 ## 使用時期 / 落とし穴 **bitmask** (部分集合列挙、状態に対する DP)、フラグ、高速算術、低レベル/組み込みコードに使用します。符号ビット、言語固有のシフト動作、可読性に注意してください — 明らかでないトリックはコメントしてください。 ## なぜ重要なのかビット操作は XOR 単一数トリックのような優雅な O(1) 空間ソリューションを生み出し、インタビューで驚かせることができます。 Bitmask DP は多くの組合せ状態空間問題を扱いやすくします。システム、グラフィックス、圧縮、および各サイクルが重要なパフォーマンスクリティカルなコードで不可欠です。