算法:常见位运算技巧总结
基础位运算
按位与 & :有0为0,无0为1
按位或 | :有1为1,无1为0
按位异或 ^ :相同为1,不同为0
按位取反 ~ :0变成1,1变成0
左移 << : 二进制序列向左移
右移 >> :二进制序列向右移
一、判断一个数n的二进制表示中的第x位是0还是1
(n >> x) & 1
n >> x 将n的第x位放到最右边第0位
与1 按位与(1的二进制序列为000000…… 1)
即可判断第x位是0还是1
二、将一个数n的二进制表示中的第x位变成1
n |= (1 << x)
要将第x位变成1,需要第x位按位或1
1 << x 造出了第x位为1,其他位为0的二进制序列
三、将一个数n的二进制表示中的第x位变成0
n &= ~(1 << x)
要将第x位变成0,需要第x位按位与0
1 << x 造出了第x位为1,其他位为0的二进制序列
对该序列取反,就早出了第x位为0,其他位为1的二进制序列
四、提取一个数n的二进制表示中的最右边的1
n & (-n)
-n 的本质是将一个二进制数最右边的1的左边区域全部变成相反的数
-n = ~n + 1
eg
n = 11010001010101100000
-n = 00101110101010011111 + 1
= 00101110101010100000
五、干掉一个数n的二进制表示中的最右边的1(变成0)
n & (n - 1)
n - 1 的本质是将一个二进制数的最右边的1的右边区域(包括自己)全部取反
eg
n = 11010001010101100000
n - 1 = 11010001010101011111
六、按位异或(^) 运算律
a ^ a = 0
a ^ 0 = a
a ^ b ^ c = a ^ c ^ b