理论

基本操作

操作	code
Get ith bit	num & (1 << i)
Set ith bit	num | (1 << i)
Flip ith bit	num ^ (1 << i)
Clear ith bit	num & (~(1 << i))
Clear bits from i	num & (1 << (i -1))
Clear bits from 0 to i	num & (-1 << (i+1))
Update ith bit	先将 ith bit cleared, 再 (num & (~(1 << i))) | value << i
Extract last bit	num & -num or num&~(num-1)
Remove last bit	num&(num-1)
Check if all bits are 1	num&(num+1) == 0
Get all 1-bits	~0
--------	-------
Set union	A | B
Set intersection	A & B
Set subtraction	A & ~B
Set negation ALL_BITS	^ A or ~A

Python 操作:

• int -> binary : int('01110', 2)
• binary -> int : bin(x)

Tips

• i&(i-1) will set the last significant bit to be zero
• mask = 0xff set all the last 32 bits to be 1.
• XOR Property:
  • a ^ a = 0
  • a ^ 0 = a

负数表达

【没看懂】 计算机实际存储 integer in two component, 第一位为0表示正书，第一位为1表示负数，如在一个bit machine上， 7可以表达为0111；而负数第一位之后的 digit=(2^(N-1)-k),N为bit of machine, 如 -1=2^3 - 7, 故-1可以表示为1111.

logit shift vs arithmetic shift

【没看懂】

• logit shift: 包含第一个符号位，全部向右移，在符号位补0， >>>
• arithmetic shift: 包含第一个符号位，全部向右移，在符号位补和原来相同的符号 >>

Reference

A summary: how to use bit manipulation to solve problems easily and efficiently

Problems

67. Add Binary化为 x+y = ((x&y)<<1) + (x+y), 其中左边项为carry, 右边为没有carry的部分，这两部分组成新的x, y， 继续相加，直至carry = 0
190. Reverse Bits将数字向右推，(即 n >> 1; and res |= last_digit_of_n << power, power = 31... 1
191. Number of 1 Bits每次res += (n&1), n向右推一格
136. Single Number用XOR
137. Single Number II（别的数字都重复3次，找到只重复1次都数字）可以用3*sum(set(nums))-sum(nums))//2 解决，但需要o(n)的空间；用bit可以将空间复杂度降到O（1）-> 从最右位开始将每bit上的数字相加，模3， 再加到结果相应的位置上，若>1<<32, 则用到了符号为，需要减去1<<32
1318. Minimum Flips to Make a OR b Equal to c从c的最后一列往前逐个判断， 若c&1==1, 则a&1和b&1中只需一个成立；若c&1==0， 则两者都不能成立
201. Bitwise AND of Numbers Range等价于找到所有数的common prefix, 等价于找到首尾数的common prefix -> left, right都向右移直至相同
1611. Minimum One Bit Operations to Make Integers Zero分为三步： 1） 1xxxx->11000, 即f(1xxxx^11000) 2)将最左位->0 3)f(10000),可以证明f(2^k)=2^(k+1)-1
【难】1915. Number of Wonderful Substringsfor i: 1）用bitmask表示以s[:i]每个字母出现的奇偶次数 2)计算以s[i]结尾的偶字串：若curr mask之前出现过freq[mask]次，则代表有freq[mask]次字串全为偶 3)计算以s[i]结尾的奇字串：对于每个mask bit, 将其flip， 由freq[mask^(1<<i)]判断之前字串为奇出现几次\

2425. Bitwise XOR of All Pairings利用XOR的两条性质\

** i&(i-1) will set the last significant bit to be zero 338. Counting Bits用 i&(i-1)消除最后个1, 又因为res[i&(i-1)]已经算过， 再+1即可
231. Power of Two判断 i&(i-1) == 0\

** mask = 0xff set all the last 32 bits to be 1. repeated-dna-sequences Robin Karp 的变种

utf-8-validation

use mask = 1>>7 + 1>>6 to fetch the first two significant bits in a 8 bit representation. 136. Single Number
137. Single Number II use a, b to record the xor of element appeared once and twice. 260. Single Number III \

【不懂】371. Sum of Two Integersa ^ b represent sum of a, and b without carry; (a & b) << 1 represent carry of sum. repeat until carry is zero.负数情况需要特殊处理

751. IP to CIDR每次由尾部开始往前直至不是0，来分段
1969. Minimum Non-Zero Product of the Array Elements

2429. Minimize XOR分别计算nums1, nums2的bit个数,c1, c2, 1) 当c1 > c2: x = c1前几位1, 剩下为0. 2)c1 <c2时，x保留num1所有1,并且从最右开始设1.\

Bit Manipulation

Number of 1 Bits cnt += x&1 every time and x >> 1.

Hamming Distance while(n) { n &=(n - 1); cnt++;} can be used to count the number of bit 1 in n, since n &=(n - 1) clear the last 1 in n.

Reverse Bits