位运算记录

发表于 更新于 分类于 ， 本文字数： 598 阅读时长 ≈ 4 分钟
位运算在算法问题中常作为一种技巧，记录下它

简介

leetcode上的解释：

位操作（Bit Manipulation）是程序设计中对位模式或二进制数的一元和二元操作。在许多古老的微处理器上，位运算比加减运算略快，通常位运算比乘除法运算要快很多。在现代编程语言中，情况并非如此，很多编程语言的解释器都对基本的运算进行了优化，因此我们在实际开发中可以不必做一些编译器已经帮我们做好的优化，而只要写出代码本身所要表现的意思。

位操作符

此处用python中的位运算操作符。

异或

相同的为0，不同的为1

python中用^表示，有如下公式：

  • a ^ a = 0
  • a ^ 0 = a
  • a ^ b = b ^ a
  • a ^ (b ^ c) = (a ^ b) ^ c

可用来检测在一个确定的序列中，寻找缺失的数字。

与

python中用&表示。

1 & 0 = 0,1 & 1 = 1,0 & 1 = 0,0 & 0 = 0

可用来判断一个数的奇偶性。

1
2
3
4
5
6
if a & 1 == 1:
    # a为奇数
    pass
elif a & 1 == 0:
    # a为偶数
    pass

或

python中用|表示。

1 & 0 = 1,1 & 1 = 1,0 & 1 = 1,0 & 0 = 0

移位

左移：<<

右移：>>

a << 1, a左移一位, 等同于 a *= 2

a << 2, a左移两位, 等同于 a *= (2**2)

a >> 1, a右移一位, 等同于 a //= 2

a >> 2, a右移两位, 等同于 a //= (2**2)