算法中常用的位操作

最近一段时间在使用py刷LeetCode的算法题,对于大神写的算法确实感到佩服,另外对于某些基础知识是有必要进行下总结的,比如今天这篇文章的主题位操作,位操作在有些情况下减少不必要的循环,从而带来成倍的性能提升,一起来看下吧。

回顾下基础概念原码、反码、补码,对于一个数, 计算机要使用一定的编码方式进行存储. 原码, 反码, 补码是机器存储一个具体数字的编码方式。原码和反码应该接触的比较多,这里重点说下补码,英语也叫two’s complement(对2求补),二进制数在内存中以补码的形式存储。

补码

补码的表示方法是: 正数的补码就是其本身 负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)

1
2
[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补

对于负数, 补码表示方式也是人脑无法直观看出其数值的。 通常也需要转换成原码在计算其数值.

取反操作

按位取反:二进制每一位取反,0变1,1变0。

1
2
3
4
5
6
7
8
9
~9的计算步骤:
转二进制:0 1001
计算补码:0 1001
按位取反:1 0110
_____
转为原码:
按位取反:1 1001
末位加一:1 1010
符号位为1是负数,即-10

1
2
3
4
5
6
7
~-9的计算步骤:
转二进制:1 1001
计算补码:1 0111
按位取反:0 1000
_____
转为原码:
正数的补码和原码相同,仍为:0 1000,即8

注意这里面进行任何的操作时,第一步是把原有的数转换成补码,因为计算机内部没有原码,只有补码,为了得到人们的理解,我们在最后转换成人们可以理解的原码。

位操作基本的用法

操作 英文 举例 说明
取并集 Set Union A|B
取交集 Set Intersection A&B
按位取反 Set Negation ALL_BITS^A or ~A 可参考上面👆的取反操作
将某位设置为1 Set Bit A |=1<<bit 将1左移bit位,然后进行按位或
将某位设置为0 Clear Bit A &=~(1<<bit) 将1左移bit位,全部取反,此时为0111..
测试某w位的值 Test Bit (A &1<<bit)!=0 将A的对应位的值与1相与,如果结果为0,则A的测试位的值为0,否则为1
删除最后一个1 Remove Last Bit A & (A-1)
获取全部为1的字节 Get ALL 1 Bits ~0 A 与 A - 1的最后一位必然不同,相与必然为0,结果使最右边一位的1设置为0(这里-1的作用是错位生1)

实例

计算给定数字的二进制1的个数

1
2
3
4
5
6
7
def count_one(n):
count = 0
while(n):
n = n & (n - 1)
count += 1

return count

^的技巧

给出一个数组,这个数组都是由不同的数字组成的,这些数字的取值从 0 到 n,请找出那个丢失的数字。当然,你也可以使用数学方法。 比如: nums = [0, 1, 3] return 2

1
2
3
4
5
6
7
def missing_number(nums):
res = 0
for i in range(len(nums)):
res ^= i
res ^= nums[i]
res ^= len(nums)
return res

|的技巧

给定一个数字 N,找出最大的 2 的幂数小于或者等于 N 的值。

1
2
3
4
5
6
7
8
def largest_power(n):
n = n | n >> 1
n = n | n >> 2
n = n | n >> 4
n = n | n >> 8
n = n | n >> 16

return n + 1 >> 1

首先将当前数字的二进制表达式中的最高位的1右边的数字全部置为1,然后再加1,向右移一位。

&的技巧

给定一个范围[m, n],其中 0 <= m <= n <= 2147483647(0x7FFFFFFF),返回指定范围内所有数字的相与结果。 比如: [5, 7] return 4

1
2
3
4
5
6
7
def rangeBitwiseAnd(m,n):
a=0
while m!=n:
m>>1
n>>1
a+=1
return m<<a

写这么一个函数:它可以返回一个无符号整型数的二进制表达式中含有 1 的个数。

1
2
3
4
5
6
def hammingWeight(n):
count=0
while(n):
n&=n-1
count+=1
return count