原码-反码-补码
- 机器数:一个数在计算机中的二进制表示叫做这个数的机器数。机器数是带符号的,在计算机中用一个数的最高位存放符号,正数为0,负数为1。
- 符号位:机器数的最高位
- 数值位:机器数的其余位
- 真值:将带符号的机器数对应的真正数值称为机器数的真值。
原码、反码、补码是机器数的不同编码方式,它们都以最高位作为符号位(0代表正数,1代表负数),它们对正数的编码完全相同,不同的只是负数和0的编码。
原码
规则:
- 正数的原码就是其自身
- 负数的原码就是符号位为1,数值位为真值绝对值
- 0的原码有两种表示,数值位全为0,符号位为0表+0,为1表-0
- 可表示范围$[-(2^{31}-1),2^{31}-1]$
1 | # 以4字节int型为例 |
反码
规则:
- 正数的反码就是其自身
- 负数的反码为其绝对值各位取反
- 0的反码有两种表示,全为0表+0,全为1表-0
- 可表示范围$[-(2^{31}-1),2^{31}-1]$
1 | # 以4字节int型为例 |
补码
规则:
- 正数的补码就是其自身
- 负数的补码为其绝对值各位取反后加1:-n = ~n + 1
- 0的补码只有一种,全为0
- 可表示范围$[-2^{31},2^{31}-1]$
1 | # 以4字节int型为例 |
计算机普遍采用补码,这是因为:
- 修复了0的重复编码,还能多表示一个最低位
- 可统一加减运算规则
补码黄金公式
补码黄金公式,对所有n都成立:
- ~(n-1) = ~n + 1是二进制数按位取补的恒等式,即是说对一个整数先减1再求反和先求反再加1得到的结果是一样的。
- -n = ~n + 1 连接了相反数和取补的关系(相反数取反加一)。
1 | 证明: |
常见数字的补码
1 | # 32位整型上界2*31-1 |
补码的加减运算
和的补码等于补码的和,若符号位有进位则丢掉:[x + y]补 = [x]补 + [y]补
1 | [33-15]补=[33]补+[-15]补 |
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 | # 截取32位二进制 |
原码、反码和补码的相互转换
三者正数的表达是一致的,对于负数三者之间的相互转化规则如下:
位运算符
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 | # 获取二进制各位 |
- 模拟乘除运算
1 | 1<<2 |
位逻辑运算符
位操作符 | 平等视角 | 主从视角 | 运算律 | ||||
---|---|---|---|---|---|---|---|
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 | # 保留A中最后一位,可用于判断整数奇偶 |
或
将某些位置为1:B为1的位置会将A对应位置置为1,其他位保持不变,因此越或越大。
1 | # 将奇数位置1 |
二进制位合并:整体上看,或运算会融合A和B中所有的1;从单个操作数来看,结果会保留本元素中所有的1,0处则取对方的数位。
1 | # 由一些二进制位拼出完整二进制序列 |
异或
- 常用公式
1 | # 交换律和结合律 |
翻转某些位:合理安排主操作数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 | # 问题1:除了一个元素出现一次,所有数字都出现了偶数次,找到该元素 |
非
- 各位取反
- 求相反数:-n = ~n + 1 = ~(n-1)
常规操作
- python处理32位整数:使用python做位运算时,谨记python的“符号位浮动”、“不存在溢出”这两大特征!
1 | # 三个有用的数 |
- bin和int的用法
1 | # bin()将整数转化为二进制字符串,有几点需注意 |
- 获取32位整型的二进制补码表示
1 | # 对应小于2**31-1的正数 |
- 如何将32位二进制补码转化为整数
1 | def bits_32nums(s): |
其他问题
1 | # 问题1:判断一个数是否为2的幂 |
位操作实现加减乘除
基于以下公式:
- -n = ~n + 1 = ~(n-1)
- 去掉整数n二进制中最右边一个1:n & (n-1),如:n=010100,n-1=010011,n&(n-1)=010000
- 仅保留整数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 | 0 + 0 = 0 |
2、各位的进位
1 | 0 + 0 = 0 |
代码一般实现
1 | # 加法-非递归 |
Python实现
因为在python中不存在溢出截断、符号位也不固定,以上减法无法得到正确结果。为了模拟C的行为,需要在每次计算完之后人为截断符号位的进位,以及将符号位固定在32位。
1 | def getSum(a,b): |
乘法运算
- 原理:
a*b = a*(2**i1+2**i2+...) = a*(1<<i1 + 1<<i2...)=a<<i1+a<<i2...
,从低到高检测b的每一位,如果是1,则在结果中累加(res += a<<i)
1 | def multiply(a,b): |
除法运算
- 原理:
x = y*(1<<i1+1<<i2...) + mod
,从高到低,减得动y<<i就减,同时把1<<i加到结果中去。1
2
3
4
5
6
7def divide(x,y):
res = 0
for i in xrange(31,-1,-1):
if x >= y<<i:
res += 1<<i
x -= y<<i
return res
参考
- [1] 原码, 反码, 补码 详解
- [2] 整型溢出
- [3] 不用加减乘除做加法中Python存在的bug