数据结构与算法:位运算

原码-反码-补码

  • 机器数:一个数在计算机中的二进制表示叫做这个数的机器数。机器数是带符号的,在计算机中用一个数的最高位存放符号,正数为0,负数为1。
  • 符号位:机器数的最高位
  • 数值位:机器数的其余位
  • 真值:将带符号的机器数对应的真正数值称为机器数的真值。

原码、反码、补码是机器数的不同编码方式,它们都以最高位作为符号位(0代表正数,1代表负数),它们对正数的编码完全相同,不同的只是负数和0的编码。

原码

规则:

  • 正数的原码就是其自身
  • 负数的原码就是符号位为1,数值位为真值绝对值
  • 0的原码有两种表示,数值位全为0,符号位为0表+0,为1表-0
  • 可表示范围$[-(2^{31}-1),2^{31}-1]$
1
2
3
4
5
6
7
# 以4字节int型为例
[1] = 00000000 00000000 00000000 000000001
[-1] = 10000000 00000000 00000000 000000001
[2147483647] = 01111111 11111111 11111111 11111111
[-2147483647] = 11111111 11111111 11111111 11111111
[+0] = 00000000 00000000 00000000 000000000
[-0] = 10000000 00000000 00000000 000000000

反码

规则:

  • 正数的反码就是其自身
  • 负数的反码为其绝对值各位取反
  • 0的反码有两种表示,全为0表+0,全为1表-0
  • 可表示范围$[-(2^{31}-1),2^{31}-1]$
1
2
3
4
5
6
7
# 以4字节int型为例
[1] = 00000000 00000000 00000000 000000001
[-1] = 11111111 11111111 11111111 11111110
[2147483647] = 01111111 11111111 11111111 11111111
[-2147483647] = 10000000 00000000 00000000 00000000
[+0] = 00000000 00000000 00000000 000000000
[-0] = 11111111 11111111 11111111 11111111

补码

规则:

  • 正数的补码就是其自身
  • 负数的补码为其绝对值各位取反后加1:-n = ~n + 1
  • 0的补码只有一种,全为0
  • 可表示范围$[-2^{31},2^{31}-1]$
1
2
3
4
5
6
# 以4字节int型为例
[1] = 00000000 00000000 00000000 000000001
[-1] = 11111111 11111111 11111111 11111111
[2147483647] = 01111111 11111111 11111111 11111111
[-2147483648] = 10000000 00000000 00000000 00000000
[0] = 00000000 00000000 00000000 000000000

计算机普遍采用补码,这是因为:

  • 修复了0的重复编码,还能多表示一个最低位
  • 可统一加减运算规则

补码黄金公式

补码黄金公式,对所有n都成立:

  • ~(n-1) = ~n + 1是二进制数按位取补的恒等式,即是说对一个整数先减1再求反和先求反再加1得到的结果是一样的。
  • -n = ~n + 1 连接了相反数和取补的关系(相反数取反加一)。
1
2
3
证明:
-n = ~n + 1 <=> -(n-1) = ~(n-1) + 1 <=> -n = ~(n-1)
-n = ~n + 1 <=> ~(-n) =~(~n+1)=~(~(n-1))=n-1 <=> n = ~(-n) + 1

常见数字的补码

1
2
3
4
5
6
7
8
9
10
# 32位整型上界2*31-1
01111111 11111111 11111111 11111111
# 1
00000000 00000000 00000000 00000001
# 0
00000000 00000000 00000000 00000000
# -1
11111111 11111111 11111111 11111111
# 32位整型下界-2**31
10000000 00000000 00000000 00000000

补码的加减运算

和的补码等于补码的和,若符号位有进位则丢掉:[x + y]补 = [x]补 + [y]补

1
2
3
4
5
6
7
8
9
10
11
[33-15]补=[33]补+[-15]补
0000 .... 0010 0001
1111 .... 1111 0001
10000 .... 0001 0010
丢掉符号位的进位得18

[3-15]补=[2]补+[-15]补
0000 .... 0000 0011
1111 .... 1111 0001
1111 .... 1111 0100<=>减1取反得绝对值:0000 .... 0000 1100
得-12

C与Python对补码处理的比较

C和python对整型数据的各种位操作都是按照对该数据的补码进行的,但是在对符号位和溢出的处理上有很大不同,这些差异可能会影响到算法移植的有效性。

  • C

    • 固定符号位:C语言中有符号整型数据在不同机器上可能是32位或64位,但无论位宽多少其符号位总是固定的
    • 可能溢出:对于unsigned整型溢出,C的规范是有定义的——“溢出后的数会以2^(8*sizeof(type))作模运算”。对于signed整型的溢出,C的规范定义是“undefined behavior”,也就是说,编译器爱怎么实现就怎么实现。
  • Python

    • 浮动符号位:python中int型数据在32位机器上位宽为32位,在64位机器上位宽为64位。自从Python2.2起,如果发生溢出,Python会自动将整型数据转换为长整型,Python中的长整型,没有指定位宽,也就是说Python没有限制长整型数值的大小,只限制于机器内存。由于其位宽不定,其补码的符号位可向外无限扩展
    • 不存在溢出:由于符号位是根据数据长度自动扩展,因此python中也不存在溢出的可能

python处理32位整数:

1
2
3
4
5
6
7
8
9
# 截取32位二进制
0xffffffff & -1
4294967295

# 补全32位二进制
'{:032b}'.format(3)
'00000000000000000000000000000011'
'{:032b}'.format(-3)
'-0000000000000000000000000000011'

原码、反码和补码的相互转换

三者正数的表达是一致的,对于负数三者之间的相互转化规则如下:

位运算符

C和python对整型数据的各种位操作都是按照对该数据的补码进行的

两种视角看待位运算符:

  • 平等视角:两个操作数地位平等
  • 主从视角:把A当做被操作数,把B当做主操作数,把A * B,看做是用B去改造A,我们只需关注B的不同构造对A的不同影响。

移位运算符

位操作符 说明 C Python 等价
x << y 左移,x左移y位 右侧补零,左侧截断 右侧补零,左侧不会溢出 x*(2**y)
x >> y 右移,x右移y位 右侧截断,左侧不定 右侧截断,左侧补符号位 x//(2**y)
  • C语言中的右移:

    • 算术移位:右移时,某些机器将对左边空出的部分用符号位填补
    • 逻辑移位:另一些机器则对左边空出的部分用0填补
  • 将某位移至指定位置

1
2
3
4
# 获取二进制各位
x = 10
for i in xrange(32):
visit(x >> i & 1)
  • 模拟乘除运算
1
2
3
4
5
6
1<<2
4
15>>3
1
-2>>222
-1

位逻辑运算符

位操作符 平等视角 主从视角 运算律
x & y 位与,都是1才是1 1处不变、0处置零 交换结合、x&x=x、x&0=0、x&1=x
x ` ` y 位或,都是0才是0 1处置1、0处不变 交换结合、x` x=x、x 0=x、x `1=x
x ^ y 位异或,一个1一个0才是1 1处取反、0处不变 交换结合、x^x=0、x^0=x、x^1=~x
~ x 按位求补,1变0,0变1

将某些位变成零:合理安排主操作数B中的1,结果中将会保留A中对应的位,而将其他位置0,起到过滤效果,因此越与越小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 保留A中最后一位,可用于判断整数奇偶
45&1
1

# 保留A中第32位,可用于提取符号位
-1>>31
-1
-1>>31 & 1
1

# 保留偶数位
22&0xAAAAAAAA
2

# 保留奇数位
22&0x55555555

# 保留第i+1位
a & 1<<i

# 保留最后一个1
n&~(n-1)

# 去掉最后一个1
n&(n-1)

# 保留最后一个字节
257 & 0xFF
1

将某些位置为1:B为1的位置会将A对应位置置为1,其他位保持不变,因此越或越大。

1
2
# 将奇数位置1
22|0x55555555

二进制位合并:整体上看,或运算会融合A和B中所有的1;从单个操作数来看,结果会保留本元素中所有的1,0处则取对方的数位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 由一些二进制位拼出完整二进制序列
res = 0
for i in xrange(32):
bit = 0
for num in nums:
bit += num >> i & 1
res |= bit % 3 << i

if res >> 31 == 1: # python 32位不是符号位,所以要手动处理
res -= 2**32
return res

#互换二进制数的奇偶位
# 先通过左移将奇数位移动到偶数位,再与0xAAAA的与运算,只保留偶数位,奇数位置零
# 再通过右移将偶数位移动到奇数位,再与0x5555的与运算,只保留奇数位,偶数位置零
# 对以上两个结果进行或运算
(n<<1)&(0xAAAA))|((n>>1)&(0x5555)

异或

  • 常用公式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 交换律和结合律
A ^ B = B ^ A
A ^ B ^ C = A ^ (B ^ C)

# 恒等率、归零律、奇偶律
X ^ 0 = X
X ^ X = 0
A ^ A ^...^ A ^ A = 奇数个就是A,偶数个就是0

# 移项
A ^ B = C <=> A = C ^ B <=> B = C ^ A

# 与-1异或相当于求反
A ^ -1 = ~A
  • 翻转某些位:合理安排主操作数B中的1,结果中将会翻转A中对应的位,而将其他位不变,达到翻转被操作数A中某些位的目的。常用的有以下几种:

  • 交换两值

    1
    2
    3
    4
    # 不用多余空间实现两值交换
    a = a ^ b
    b = a ^ b
    a = a ^ b
  • 判断序列中某元素出现次数的奇偶性
1
A ^ A ^...^ A ^ A = 奇数个就是A,偶数个就是0
  • 整型数组中寻找出现特殊次数的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 问题1:除了一个元素出现一次,所有数字都出现了偶数次,找到该元素
# 解法:只需求出所有数字的异或结果就是那个只出现一次的数字
A ^ B ^ C ^ B ^ C ^ D ^ A
= A ^ A ^ B ^ B ^ C ^ C ^ D
= 0 ^ 0 ^ 0 ^ D
= 0 ^ D
= D

# 问题2:除了两个数字出现一次,其他数字都出现两次,找到这两个元素
# 解法:① 先求所有元素的异或,得到这两个数的异或,获取该异或最右侧的1,说明这两个元素在该位上不同;
# ② 筛选所有该位为1的元素,求其异或就可以得到该位为1的那个出现一次的数;
# ③ 然后用该数与第一步得到的值进行异或就可得到另外一个数;
xor = 0
for num in nums:
xor ^= num
last1 = xor & ~(xor-1)
xo = 0
for num in nums:
if last1 & num:
xo ^= num
return [xo,xo^xor]

# 问题3:除了一个数字出现1次,其他数字都出现了3次
# 解法:把所有整数的每一位分别相加后对3取余,即得到该数字的各个二进制位,然后再把二进制位合并转化为数值
# 该方法可以作为求解“只有一个数字出现1次,其他都出现了N次的问题(N>1)”
def singleNumber(nums):
"""
:type nums: List[int]
:rtype: int
"""
res = 0
for i in xrange(32):
bit = 0
for num in nums:
bit += num >> i & 1
res |= bit % 3 << i

if res >> 31 == 1: # python 32位不是符号位,所以要手动处理
res -= 2**32
return res

  • 各位取反
  • 求相反数:-n = ~n + 1 = ~(n-1)

常规操作

  • python处理32位整数:使用python做位运算时,谨记python的“符号位浮动”、“不存在溢出”这两大特征!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 三个有用的数
mask = 0xFFFFFFFF # 掩码,用于截断、按位取反
MIN_INT = 0x80000000 # 32位最小负数
MIN_MAX = 0x7FFFFFFF # 32位最大正数

# 32位截断
a & 0xFFFFFFFF

# 32位取反
a ^ 0xFFFFFFFF

# 获取符号位
a >> 31 & 1

# 32位正整数:不溢出
# 在不超出0x7FFFFFFF的范围内,python正整数和C语言signedint机器数一致

# 超出0x7FFFFFFF,python不会溢出,也不会截断
2**32
4294967296

# 32位负整数:浮动符号位
# 在不超出0x80000000范围内将python负数转化为32位负数,直接截断即可。截断后的二进制在python中会被当做是一个正数,在C语言中则是与截断前真值相等的负整数
-1&0xFFFFFFFF
4294967295

# 将32位负数转化为python负数,高位需要补1;
# 或者从另一个角度看,因为它们的正数表示是一致的,可以先将负数转化为绝对值,再转化为python中的负数
~(a^mask+1)+1 = ~(a^mask)
~(4294967295^0xFFFFFFFF)
-1
  • bin和int的用法
1
2
3
4
5
6
7
8
9
10
11
# bin()将整数转化为二进制字符串,有几点需注意
# ① 返回的二进制字符串只显示第一个1后面的二进制位,不显示更高位
bin(255)
'0b11111111'
# ② 返回的二进制字符串以原码形式表示,正数以0b开头,负数0b前面有负号,可能是因为浮动符号位的原因,无法全部显示出来
bin(-255)
'-0b11111111'

# int(str,2)将字符串转化为对应的整数,0b可带可不带
int('-11111111',2)
-255
  • 获取32位整型的二进制补码表示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 对应小于2**31-1的正数
'{:0>32b}'.format(255)
'00000000000000000000000011111111'
# 负数不行
'{:0>32b}'.format(-1)
'000000000000000000000000000000-1'

# 自定义方法
def get32bits(num):
res = ''
for i in xrange(31,-1,-1):
res += str(num >> i & 1)
return res

# 将python的整数转化为补码形式的二进制字符串之后,可方便的利用字符串方法求解二进制的一些问题
  • 如何将32位二进制补码转化为整数
1
2
3
4
5
6
7
8
def bits_32nums(s):
res = 0
for i in xrange(32):
res <<= 1
res |= int(s[i])
if res >> 31 == 1: # python 32位不是符号位,所以要手动处理
res -= 2**32
return res

其他问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 问题1:判断一个数是否为2的幂
# 解法:是2的幂<=>首位为1其他位为0<=>
n!=0 and not n&(n-1)

# 问题2:判断一个数是否为4的幂
# 解法:是4的幂<=>是2的幂,且1在奇数位<=>
n!=0 and not n&(n-1) and n&0x55555555 == n

# 问题3:不用条件判断求绝对值
# 解法:非负数直接返回,负数,-n = ~n + 1=n^-1 - (-1)
def bit_abs(num):
negative = num >> 31
return (num ^ negative) - negative

# 问题4:按整数位求解一般问题
???

位操作实现加减乘除

基于以下公式:

  1. -n = ~n + 1 = ~(n-1)
  2. 去掉整数n二进制中最右边一个1:n & (n-1),如:n=010100,n-1=010011,n&(n-1)=010000
  3. 仅保留整数n二进制中最后一个1:n & ~(n-1),如:n=010100,则~(n-1)=101100,n&~(n-1)=000100
运算 原理
加法 a+b = a^b + (a&b)<<1
减法 a-b = a + ~(n-1)
乘法 a*b = a*(1<<i1+1<<i2...)
除法 a = b*(1<<imax + 1<i2...)+mod

加减运算

原理:将加法计算分解为两部分:①计算不进位的结果,②是计算各位的进位,然后再将两者相加即得到结果。a,b = a^b,(a&b)<<1

1、不进位的结果

1
2
3
4
5
6
7
8
9
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0
这个过程可以用异或运算实现:
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

2、各位的进位

1
2
3
4
5
6
7
8
9
0 + 0 = 0
0 + 1 = 0
1 + 0 = 0
1 + 1 = 10
这个过程可以用位与和移位来实现:
0 & 0 = 0 (0 & 0)<<1 = 0
0 & 1 = 0 (0 & 1)<<1 = 0
1 & 0 = 0 (1 & 0)<<1 = 0
1 & 1 = 1 (1 & 1)<<1 = 10

代码一般实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 加法-非递归
def getSum(a,b):
while b:
a,b = a^b, (a&b)<<1
return a
# 加法-递归
def getSum(a,b):
if b:
return getSum(a^b,(a&b)<<1)
else:
return a

# 减法a-b=a+(-b)=a+(~b+1)
def subtraction(a,b):
return getSum(a,getSum(~b,1)

Python实现
因为在python中不存在溢出截断、符号位也不固定,以上减法无法得到正确结果。为了模拟C的行为,需要在每次计算完之后人为截断符号位的进位,以及将符号位固定在32位。

1
2
3
4
5
6
7
def getSum(a,b):
MAX = 0x7FFFFFFF # 32位整型最大值
MIN = 0x80000000 # 32位整型最小值
mask = 0xFFFFFFFF
while b != 0:
a, b = (a ^ b) & mask, ((a & b) << 1) & mask # 截断32位
return a if a <= MAX else ~(a ^ mask) # 如果为负数,先按补码划为正数再划为负数~(a^mask+1)+1= ~(a^mask)

乘法运算

  • 原理:a*b = a*(2**i1+2**i2+...) = a*(1<<i1 + 1<<i2...)=a<<i1+a<<i2...,从低到高检测b的每一位,如果是1,则在结果中累加(res += a<<i)
1
2
3
4
5
def multiply(a,b):
res =0
for i in xrange(32):
if b&(1<<i):res += a<<i
return res

除法运算

  • 原理:x = y*(1<<i1+1<<i2...) + mod,从高到低,减得动y<<i就减,同时把1<<i加到结果中去。
    1
    2
    3
    4
    5
    6
    7
    def divide(x,y):
    res = 0
    for i in xrange(31,-1,-1):
    if x >= y<<i:
    res += 1<<i
    x -= y<<i
    return res

参考

坚持原创技术分享,您的支持将鼓励我继续创作!