01.位运算知识

位运算知识 #

1. 位运算简介 #

位运算(Bit Operation):在计算机内部,数是以「二进制(Binary)」的形式表示的。位运算就是直接对数的二进制进行计算操作,在程序中使用位运算进行操作,会大大提高程序的性能。

  • 二进制数(Binary):用 01 两个数码来表示的数,它的基数是 2,进位规则是「逢二进一」,借位规则是「借一当二」。例如,十进制中的 1234 对应的二进制数分别为 001010011100

二进制数中的每一位数字称为「位(Bit)」, 3 位所能表示的最大二进制数是 111,也就是十进制中的 7,即 $1 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 7$。

在二进制的基础上,我们可以对二进制数进行相应的位运算。基本的位运算共 6 种,分别是:「按位与」、「按位或」、「按位异或」、「按位取反」、「左移」和「右移」。

2. 位运算基础操作 #

2.1 按位与运算 #

按位与运算(AND):按位与运算符 & 是双目运算符。其功能是对两个二进制数的每一个二进制位相与。只有对应的两个二进值位都为 1 时,结果位才为 1。当参与运算的是负数时,参与两个数均以补码出现。

  • 按位与运算规则:
    • 1 & 1 = 1
    • 1 & 0 = 0
    • 0 & 1 = 0
    • 0 & 0 = 0

例如,十进制中的 35 进行按位与运算,则结果如图所示:

按位与运算的通常用法:

  1. 清零:任何数与 0 做按位与运算结果都为 0
    • (x & 0) == 0
  2. 取指定位:比如要取一个数的低 4 位,则只需使用该数与二进制数 00001111 (后 4 位为 1)做按位与运算,结果就是这个数的低 4 位的值。
  3. 奇偶判断:通过与 1 进行按位与运算,即可判断某个数是奇数还是偶数。
    • (x & 1) == 0 为偶数,(x & 1) == 1 为奇数。

2.2 按位或运算 #

按位或运算(OR):按位或运算符 | 是双目运算符。其功能对两个二进制数的每一个二进制位相或。只要对应的 2 个二进位有一个为 1 时,结果位就为 1。当参与运算的是负数时,参与两个数均以补码出现。

  • 按位或运算规则:
    • 1 | 1 = 1
    • 1 | 0 = 1
    • 0 | 1 = 1
    • 0 | 0 = 0

例如,十进制中的 35 进行按位或运算,则结果如图所示:

按位或运算的通常用法:

  1. 将某位设置为 1:比如需要将一个数的低 4 位设置为 1,则只需使用该数与二进制数 00001111 (后 4 位为 1) 做按位或运算即可得到。

2.3 按位异或运算 #

按位异或运算(XOR):按位异或运算符 ^ 是双目运算符。其功能是对两个二进制数的每一个二进制位相异或。如果某位不相同则该位为 1,如果某位相同则该位为 0。当参与运算的是负数时,参与两个数均以补码出现。

  • 按位异或运算规则:
    • 0 ^ 0 = 0
    • 1 ^ 0 = 1
    • 0 ^ 1 = 1
    • 1 ^ 1 = 0

例如,十进制中的 35 进行按位异或运算,则结果如图所示:

按位异或运算的通常用法:

  1. 翻转指定位:比如需要将一个数的低 4 位进行反转,则只需使用该数与二进制数 00001111 (后 4 位为 1) 做按位异或运算即可得到。
  2. 0 相异或值不变:一个数与 0 做按位异或运算的结果不变。例如,10101100 ^ 00000000 = 10101100
  3. 交换两个数:通过按位异或运算可以实现交换两个数的目的。
1
2
3
4
5
a, b = 10, 20
a ^= b
b ^= a
a ^= b
print(a, b)

2.4 按位取反运算 #

按位取反运算(NOT):按位取反运算符 ~ 是单目运算符。其功能是对一个二进制数的每一个二进制位取反。使数字 1 变为 00 变为 1。当参与运算的是负数时,参与的该数以补码出现。

  • 按位取反运算规则:
    • ~0 = 1
    • ~1 = 0

例如,十进制中的 3 进行按位取反运算,则结果如图所示:

2.5 按位左移运算 #

按位左移运算(SHL): 按位左移运算符 << 是双目运算符。其功能是对一个二进制数的各个二进制位全部左移若干位(左边的二进制位丢弃,右边末尾补 0)。

例如,十进制中的 3 进行左移 1 位运算,则结果如图所示:

2.6 按位右移运算 #

按位右移运算(SHR): 按位右移运算符 >> 是双目运算符。其功能是对一个二进制数的各个二进制位全部右移若干位(右边的二进制位丢弃,正数左边开补 0,负数左边补 1)。

例如,十进制中的 3 进行右移 1 位运算,则结果如图所示:

2. 位运算的应用 #

2.1 位运算的常用应用 #

功 能 位运算 示例
去掉最后一位 x >> 1 101101 -> 10110
在最后加一个 0 x << 1 101101 -> 1011010
在最后加一个 1 (x << 1) + 1 101101 -> 1011011
把最后一位变成 1 x | 1 101100 -> 101101
把最后一位变成 0 x | 1 - 1 101101 -> 101100
最后一位取反 x ^ 1 101101 -> 101100
把右数第 k 位变成 1 x | (1 << (k - 1)) 101001 -> 101101, k = 3
把右数第 k 位变成 0 x & ~(1 << (k - 1)) 101101 -> 101001, k = 3
右数第 k 位取反 x ^ (1 << (k - 1)) 101001 -> 101101, k = 3
取末尾 3 x & 7 1101101 -> 101
取末尾 k x & 15 1101101 -> 1101, k = 4
取右数第 k x >> (k - 1) & 1 1101101 -> 1, k = 4
把末尾 k 位变成 1 x | (1 << k - 1) 101001 -> 101111, k = 4
末尾 k 位取反 x ^ (1 << k - 1) 101001 -> 100110, k = 4
把右边连续的 1 变成 0 x & (x + 1) 100101111 -> 100100000
把右边起第一个 0 变成 1 x | (x + 1) 100101111 -> 100111111
把右边连续的 0 变成 1 x | (x - 1) 11011000 -> 11011111
只保留右边连续的 1 (x ^ (x + 1)) >> 1 100101111 -> 1111
去掉右边起第一个 1 的左边 x & (x ^ (x - 1))x & (-x) 100101000 -> 1000
从右边开始,把最后一个 1 改写成 0 x & (x - 1) 100101000 -> 100100000

2.1 Brian Kernighan 算法 #

参考资料 #

本站总访问量  次  |  您是本站第  位访问者