位运算技巧和实例
2019-03-24 本文已影响0人
zestloveheart
概述
- 在计算机中所有数据都是以二进制的形式储存的。位运算其实就是直接对在内存中的二进制数据进行操作，因此处理数据的速度非常快。
- 位操作只能用于整形数据，对float和double类型进行位操作会被编译器报错。
| 符号 | 作用 |
|---|---|
| & | 与 |
| | | 或 |
| ~ | 非 |
| ^ | 异或 |
| << | 左移：高位丢弃，低位补0 |
| >> | 右移：对无符号数，高位补0 |
入门技巧
-
判断奇偶 i & 1
若i为奇，则为1；10101 & 00001 = 00001
若i为偶，则为0；10110 & 00001 = 00000 -
交换变量 a ^= b；b ^= a；a ^= b；
-
变号 ~a + 1
-
绝对值
a = 10 或者 -50
i = a >> 31
a = (a ^ i) - i
- 设置第n位
设为1：y = x | (1<<n)
设为0：y = x & ~(1<<n)
取反：y = x ^ (1<<n)
简单技巧
- 高低位互换：a = (a >> 8) | (a << 8)
- 二进制逆序：使用归并排序 和 1中的技巧
- 将最右边的1的设为0：y = x & (x-1)
- 统计二进制中1的个数，利用3的技巧：
count = 0
while n:
count += 1
n = n & (n - 1)
系列问题：在数组里面找只出现一次的数字
- 在其他数字都出现2次的数组里面找到唯一只出现1次的数
思路：全部异或一次，相同的会抵消，最后剩下的就是ans
a = [1,2,2,1,3,5,5]
ans = 0
for i in a:
ans ^= i
- 在其他数字都出现2次的数组里面找到唯二只出现1次的数
思路：全部异或，最后剩下的是ans = ans1 ^ ans2，找到ans第一个1，即代表ans1和ans2在该位肯定不同，一个取0，一个取1。把数组依据这一位是0还是1分为两个数组就能将ans1和ans2分开，再对两个数组分别进行异或即可得到ans1和ans2。
array = [1, 1, 2, 2, 5, 3]
ans = 0
for i in array:
ans ^= i
position = 0
while ans:
if (ans >> position)&1:
break
position+=1
ans1,ans2 = 0,0
for i in array:
if (i >> position)&1:
ans1 ^= i
else:
ans2 ^= i
print(ans1,ans2)
- 在其他数字都出现
次的数组里面找到唯一只出现1次的数
# 法1：对正数有效
array = [2,2,2,5,5,5,4,4,4,10]
counts = [0]*32
for num in array:
i = 0
while num>>i:
counts[i]+=(num>>i)&1
i+=1
ans = 0
for i,count in enumerate(counts):
if count % 3 != 0 :
ans += (1 << i)
print(ans)
# 法2：皆有效
ones , twos = 0 , 0
for i in array:
ones = ones ^ i & ~twos
twos = twos ^ i & ~ones
print(ones)
不使用加减乘除运算符计算
- 加法
def add_bit(a,b):
x,y = a^b,(a & b) << 1
while y:
x,y = x^y,(x & y) << 1
return x
- 乘法
def mul_bit(a,b):
ans = 0
while b:
if b & 1:
ans = add_bit(ans,a)
a<<=1
b>>=1
return ans
