常见的位运算技巧

约 7 分钟

简要介绍了计算机中整数二进制的存储方式，以及算法题中常见的位运算技巧

本页目录

什么是位运算？

位运算是整数之间的运算,将十进制整数转化为二进制后,按位进行AND(&),OR(|),XOR(^),NOT(~)等逻辑运算,或者整体进行<<,>>等左右移位运算.

注意到我说了整数,而不是非负整数.那计算机,尤其是python里,如何存储一个负数的二进制表示呢？

负数的二进制

以下内容均为在python中的情况.python中,整数其实自带符号这一属性.然而为了在位运算中自洽的模拟,思想上,我们假设python中存储的二进制没有固定长度,因此,除了表示数字之外,前面的无限个数字都用来表示符号,比如7的表示就是… 0000 0111

有一个名字叫补码,我很反感.我试图揣测当年设计师的思路,给出一个合理的表示负数的方法

  • 首先,负数应该与正数一一对应,且做出区分.在十进制中,人类让数字部分相同,符号部分作+和-两种来区分,比如-2对应+2,等等
  • 其次,不能与先前的位运算冲突,比如<<表示乘以2,>>表示除以2再向下取整
  • 最重要的,0,不应该和-0混淆.这两个数字就应该是一样的.人类能直观的把-0自动看作0,但是计算机不能

因此,在计算机中,光靠额外的一位数字存储正负号,会带来很大的麻烦,这不是一个很好的设计

于是,设计师一拍大腿:你不是要一一对应吗？那我在负数里面,索性把0和1的含义互换,用1表示空缺,用0表示占位,这样,正负数自然就区分开来

可是0依旧是问题.按照这种思路,…. 0000 0000表示+0, …1111 1111表示-0.怎么办？人为的把负数往后移动一位就好了！让… 1111 1111去表示-1, …. 1111 1110去表示-2, 等等.

这样,想要看懂一个负数的二进制,只需要:

  • 把0和1反写
  • 加1

得到的数字就是这个负数的数字部分,或者说相反数

这么做,三条规则都满足了吗？

  • 正负数能区分,满足
  • <<依旧表示乘以2
    • 在末尾补上0后,相当于对他取反后的结果乘以2再加1
    • 记原本取反的结果为a,那这个数字的数字部位就是a+1
    • 移位后取反的结果就是2a+1, 这个数字的数字部位就是2a+1+1=2(a+1)
    • 符号不变,数字部位恰好变为原来的2倍
  • >> 依旧表示//2
    • 去掉最后一位数,相当于去掉取反后的结果的最后一位数
    • 记原本取反后的数字是a, 那么原数的数字部位就是a+1
    • 去掉最后一位数字后结果就是a//2, 原数的数字部位就是a//2 + 1
    • 假设a为奇数,那么(-(a+1))//2 = (-2k-2)//2 = -k-1 = -(a//2 +1)
    • 假设a为偶数,那么(-(a+1))//2 = (-2k-1)//2 = (-2k-2)//2 = -k-1 = -(a//2 +1)
    • 依旧成立,注意对负的奇数//2操作,比如-5//2=-3而非(-5)//2

比如数字… 1111 1010, 按照这种方式变换:

  • 取反:…. 0000 0101
  • 加一:…. 0000 0110

…. 0000 0110 正是6,因此-6的二进制表示就是… 1111 1010

你可能会疑惑,电脑怎么知道… 1111 1010是-6还是一个很大的数字?

  • 在python中,这个问题不存在,因为python自带符号属性
  • 在其他语言,比如C中,数字是有长度限制的,因此最开头一个数"充当了"正负号的显示器.同时,你在声明变量的时候,就已经确定了这个数字带不带符号了.同一个1111 1010, 你赋值给没有符号的变量,它就是250;赋值给带符号的变量,它就是-6.
  • 因此完全没必要担心,这种方法就是无比的出色

取反的本质

我先问你一个问题,15的二进制表示是…. 0000 1111, 对15取反,得到多少？

  1. 0,因为… 0000 1111取反后变成了….1111 0000, 原来的15只用了最右端四位数字,因此取反后的数字就是最右端的四位数字,即-0=0
  2. -16,因为取反后的结果….1111 0000是一个负数,因此0和1需要反过来看,此外还要加上1,因此是-(15+1)=-16
  3. -32,取反后….1111 0000的后四位是0,前面都是1,这表示-0,不合法,因此需要往前额外借一个1,得到的数字就是-32

选择1和3的读者,建议先去消化上一段:负数的二进制表示

在谈及负数的二进制表示时,我们已经知道:获取一个负二进制数的数字部分,第一步就是"取反".那时我们认为,取反就是把1变成0,把0变成1.然而,你有没有发现,取反后的结果加上原来的结果,必然是一个全1的二进制数字, 也就是-1:～n+n= … 1111 1111=-1. 这对于所有数字都是成立的,因为所有数字都是由0和1组成的,无出其右.这将是继-n+n=0之后,又一个值得记忆的公理

移项后得到~n=-1-n, 就是取反操作的数学本质,其余所有貌似合理的解释都是狗屁,不用管.

常见技巧

1. 利用取反实现加1与减1

我们知道了一个整数加上它取反的结果等于-1,根据这个-1,能创造出+1与-1的效果

  • -~n=-(-1-n)=n+1, 就是加一操作
  • ~-n=-1-(-n) =n-1, 就是-1操作

2. 异或的性质

  • a ^ a = 0
  • a ^ 0 = a
  • a ^ -1 = ~a

3. 利用异或判断数字是否同号

正数的符号是0,负数的符号是1,正负号不同的两个数进行异或运算,得到的符号一定是1,也就是负数.因此,x^y≥0表明两者同号(当且仅当x=y取等),x^y < 0表明两者异号

4. 利用AND和移位提取二进制的第k位

AND运算有这样的性质

  • 与1运算保持不变:0 & 1 = 0, 1 & 1 = 1
  • 与0运算变为0: 0 & 0= 0, 1 & 0 = 0

我们可以人为的利用一个仅在第k位为1的数字,提取出原数的第k个数字:

python
>>> a = 15
>>> k = 3
>>> bin(a)
'0b1111'
>>> bin(a & (1 << (k-1)))
'0b100'

5. 利用AND判断奇偶性

很简单,最后一位是1,就是奇数;是0,就是偶数,对负数也恰好是一样的

python
>>> a = 15
>>> a & 1
1
>>> (a+1) & 1
0

6. 利用OR将第k位修改为1

OR运算有这样的性质

  • 与0运算,保持不变:1 | 0 = 1, 0 | 0 = 0
  • 与1运算,永远是1: 1 | 1 = 1, 0 | 1 = 1

可以利用这点,将指定位置的任意数字变成1

python
>>> a = 9
>>> bin(a)
'0b1001'
>>> bin(a | (1 << (k-1)))
'0b1101'

7. 利用异或反转第k位

OR运算有这样的性质

  • 与0运算,保持不变:1 ^ 0 = 1, 0 ^ 0 = 0
  • 与1运算,反转数字: 1 ^ 1 = 0, 0 ^ 1 = 1

可以利用这点,将指定位置的任意数字反转

python
>>> a = 13
>>> bin(a)
'0b1101'
>>> bin(a ^ (1 << (k-1)))
'0b1001'

比如力扣2997题 这题就利用了异或的交换律,与异或反转的技巧.对每一个具体数字的操作,就相当于是对整体的操作.因此,只需要看从数组整体异或的结果到k,需要反转几位数就可以了

python
class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        return reduce(xor, nums, k).bit_count()

8. 利用AND和取反将第k位修改为0

换一个角度利用AND的效果

  • 与1运算,保持不变:0 & 1 = 0, 1 & 1 = 1
  • 与0运算,永远是0: 0 & 0= 0, 1 & 0 = 0

这回我们创建一个全是1,只有第k位是0的二进制数字

python
>>> a = 15
>>> k = 3
>>> bin(a)
'0b1111'
>>> bin(a & ~(1 << (k-1)))
'0b1011'

9. 利用AND消除最后一个1

减1后会把最后一个1变成0,原本最后一个1后面所有的数字变成1.这导致从最后一个1及其后面的所有数字都与原数是反的.根据AND运算,不同的数字运算得到0,这达成了消除最后一个1的效果

python
>>> a = 14
>>> bin(a)
'0b1110'
>>> bin(a & (a-1))
'0b1100'
标签算法

继续阅读

返回文章列表