天池Python练习02-位运算
目录
1位运算
1.1原码 反码 补码
1.2按位非操作 ~
1.3按位与操作 &
1.4按位或操作 |
1.5按位异或操作 ^
1.6按位左移操作 <<
1.7按位右移操作 >>
1.8利用位运算快速计算
1.9利用位运算实现整数集合
1位运算
1.1原码 反码 补码
二进制有三种不同的表示形式:原码 反码 补码。计算机内部使用补码来表示
符号位 最高位为符号位 0表示正数 1表示复试
位运算中符号位也参见运算
原码 就是其二进制的表示 (有一位符号位)
0 0 00 00 11 -> 3
1 0 00 00 11 -> -3
反码 正数的反码就是原码 负数的反码符号位不变 其余位取反
0 0 00 00 11 -> 3
1 1 11 11 00 -> -3
补码 正数的补码就是原码 负数的补码是反码+1
0 0 00 00 11 -> 3
1 1 11 11 01 ->-3
1.2按位非操作 ~
~ 把补码中的0和1全部取反 有符号位的整数的符号位在运算中同样会取反
~ 1 = 0
~ 0 = 1
0 0 00 01 01 -> 5
~
1 1 11 10 10 ->-6
1 1 11 10 11 ->-5
~
0 0 00 01 00 -> 4
1.3按位与操作 &
两个对应全为1才为1
1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0
0 0 00 01 01 -> 5
&
0 0 00 01 10 -> 6
0 0 00 01 00 -> 4
1.4按位或操作 |
两个对应有一个为1就为1
1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0
0 0 00 01 01 -> 5
|
0 0 00 01 10 -> 6
0 0 00 01 11 -> 7
1.5按位异或操作 ^
两个对应不同时为1
异或操作满足交换律和结合律
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
A:00 00 11 00
B:00 00 01 11
A^B:00 00 10 11
B^A:00 00 10 11
A^A:00 00 00 00
A^0:00 00 11 00
A^B^A = A^A^B = 00 00 01 11
1.6按位左移操作 <<
将二进制表示向左移动i位 后面补0
00001011 -> 11
11 << 3
01011100 -> 88
1.7按位右移操作 >>
将二进制表示向右移动i位 前面补0
00001011 -> 11
11 >> 2
00000010 ->2
1.8利用位运算快速计算
通过<< >> 快速计算2的倍数的问题
n << 1 -> 计算n*2
n >> 1 -> 计算n/2 负奇数运算不可用
n << m -> 计算n*(2^m) 既乘以2的m次方
n >> m -> n*(2^m) 既除以2的m次方
1 << n -> 2^n
通过^快速交换两个整数
a ^= b
b ^= a
a ^= b
通过a & (-a) 快速获取a的最后为1位置的整数
00 00 01 01 ->5
&
11 11 10 11 ->-5
00 00 00 01 ->1
00 00 11 10 ->14
&
11 11 00 10 ->-14
00 00 00 10 ->2
1.9利用位运算实现整数集合
一个数的二进制表示可以看成是一个集合(0表示不在集合内 1表示在集合内)
设从右向左表示0~9
比如集合{1,3,4,8}可以表示为 01 00 01 10 10 而对应为位运算可以看做是对集合进行的操作
元素与集合的操作:
a | (1<<i) -> 把i插入到集合中
a & ~(1<<i) -> 把i从集合中删除
a & (1<<i) -> 判断i是否属于该集合(0不属于,非零属于)
集合之间的操作:
a 补 -> ~a
a 交 b -> a & b
a 并 b -> a | b
a 差 b -> a & (~b)
python的bin()输出
print(bin(3))
>>>0b11
print(bin(-3))
>>>-0b11
print(bin(-3 & 0xffffffff))
>>>0b11111111111111111111111111111101
print(bin(0xfffffffd))
>>>0b11111111111111111111111111111101
print(0xfffffffd)
>>>4294967293
我们从结果可以看出:
1. Python中 bin 一个负数(十进制表示),输出的是它的原码的二进制表示加上个负号,巨坑。
2. Python中的整型是补码形式存储的。
3. Python中整型是不限制长度的不会超范围溢出。
所以为了获得负数(十进制表示)的补码,需要手动将其和十六进制数 0xffffffff 进行按位与操作,再交给 bin() 进行输出,得到的才是负数的补码表示。