位运算
移位运算
[1 << n Longleftrightarrow 2^n
]
[1 >> x Longleftrightarrow frac n {2^x}
]
lowbit运算
int lowbit(int x) {
return x & (-x);
}
二进制的状态压缩
- 取出整数n在二进制表示下的第k位:
n >> k & 1
- 在n的二进制表示下的第k位赋值为1:
n | ( 1 << k )
- 在n的二进制表示下的第k位赋值为0:
n & (~ 1 << k)
- 在n的二进制表示下的第k位取反:
n xor (1 << k)