位运算总结

与运算

判断某一位是否为1

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

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

相关题目:

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

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

这种技巧常常使用在:

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

  • 判断数字中是否只有1个1, 即该数字是否是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; 相同的三个数字进行异或, 得到的原来的数字

求和

两数求和

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

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

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

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

参考:

找数组中的异常数字

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

数字关系

整除

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

奇偶

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

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

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

Python中的位运算

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

a = 0011 1100 = 60

b = 0000 1101 = 13

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

运算符

描述

&

按位与运算符

|

按位或运算符

^

按位异或运算符

~

按位取反运算符, ~x 类似于 -x-1

<<

左移动运算符, 运算数的各二进位全部左移若干位, 由 << 右边的数字指定了移动的位数, 高位丢弃, 低位补0

>>

右移动运算符, 把 >> 左边的运算数的各二进位全部右移若干位, >> 右边的数字指定了移动的位数

上一页位运算下一页[67][简单] 二进制求和

最后更新于

这有帮助吗？