位运算总结

与运算

判断某一位是否为1

需要判断某个数字的第$i^{th}$位是否为1, 使用只有第$i^{th}$位为1的掩码, 与该数字相与, 如果结果不为0, 则该位置为1.

得到掩码的方法是将1左移$i-1$次.

相关题目:

• [191][简单] 位1的个数

将数字的最后一个1位反转为0

对于任意数字$n$, 将$n$与$n-1$相与, 就可以把数字$n$的最后一位变为0.

这种技巧常常使用在:

• 计算一个数字中一比特数的数量, 就不需要将所有的位遍历一边了. 只需要不断地将最低的1位置0, 并统计数字, 直到所有的1都被置零, 此时数字就等于0了, 停止

• 判断数字中是否只有1个1, 即该数字是否是2的幂

相关题目:

• [191][简单] 位1的个数

• [338][中等][动态规划] 比特位计数

• [461][简单] 汉明距离

• [231][简单] 2的幂

提取最低位的1

n & (-n)

-n是n的相反数, 负数在二进制中是按照补码规则在计算机中存储的, -n的二进制表示为n的二进制表示的每一位取反再加上1. 因此n中最低位的1取反为0, 这之前的位原来都是0, 取反之后都是1. 加上1之后, 这些位置都会进位变成0, 原来最低位的1又会变为1. 而更高位的数字都是反转的, 因此将n与它的相反数-n相与, 得到的就是n中最低位的1代表的数值.

• [231][简单] 2的幂

异或运算

• 异或运算满足结合律.

• 相同的数字进行异或, 得到的结果为0; 相同的三个数字进行异或, 得到的原来的数字

  • 题目: [268][简单] 缺失数字

求和

两数求和

对于两个数字a和b, 有:

• a^b: 每位的异或运算, 得到的结果为无进位相加的结果

• a&b左移一位: 每位的与运算, 得到的结果为进位结果

因此将这a^b与a&b左移一位相加, 得到的仍然是a+b. 左移一位的目的是实现进位.

参考:

• [67][简单] 二进制求和
• [剑指Offer-65][简单] 不用加减乘除做加法

找数组中的异常数字

在反复出现数字组成的数组中, 找到其中异常的数字, 即独立出现, 或出现次数异常的数字.

• [136][简单] 只出现一次的数字
• [137][中等] 只出现一次的数字 II
• [260][中等] 只出现一次的数字 III

数字关系

整除

无论奇偶数, 将其二进制表示左移一位, 等价于将其二进制表示的最低位去掉, 这个数字也可以由整除得到$\lfloor \frac{x}{2} \rfloor$

奇偶

• 奇数的最后一位为1, 偶数的最后一位为0, 因此判断一个数是否是奇偶数, 可以将其于1相与, 为1则为奇数

• 奇数中的一比特数, 可以由它紧邻的之前的偶数中一比特数再加1得到

• 偶数中的一比特数, 就是它的一半$\frac{x}{2}$对应的一比特数, 因为将$\frac{x}{2}$右移相当于乘以二

Python中的位运算

Python中低位在右, 高位在左, 因此将一个数向右移一位是在求整除2的结果, 左移一位是在将这个数字乘以2.

a = 0011 1100 = 60

b = 0000 1101 = 13

Python中支持的位运算符如下:

运算符	描述
&	按位与运算符
|	按位或运算符
^	按位异或运算符
~	按位取反运算符, ~x 类似于 -x-1
<<	左移动运算符, 运算数的各二进位全部左移若干位, 由 << 右边的数字指定了移动的位数, 高位丢弃, 低位补0
>>	右移动运算符, 把 >> 左边的运算数的各二进位全部右移若干位, >> 右边的数字指定了移动的位数