基本概念

位元運算 - HackMD

n-1 → 把n的二進制表示的「最右邊的1」變為0，接著把其後的所有0變為1

4-1 → 100 → 011

重複執行 n & n-1 可以用來求一個數有幾個1

n-1 後，會把最後邊的1轉成0，然後把後面所有0轉成1 在與n做&之後，最右邊的1以前所有bit都不會變，該bit之後通通變成0 → 形同只翻轉最後邊的1 → 重複3次，表示翻轉最後邊的1三次，表次總共有3個1 n = 1100100 n-1 = 1100011 n&n-1 = 1100000

191. Number of 1 Bits

461. Hamming Distance

一個非零數字 XOR 另外一個數字兩字，會變回自己

a ⊕ b ⊕ b = a

因為一個數字 XOR 兩次，會變 0，且任何數 XOR 0 會等於自己

136. Single Number

如果要一個一個bit 看，可以用這招

for i in range(31):
		if (n >> i) & 1:
		...

n 往右 shift i 個表示把目前關注的 bit 移到最右邊