跳转至

位运算

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/bit-manipulation-and-math/o2gjqv/
来源：力扣（LeetCode）

一、整数在计算机中的表示方式

1、计算机中的二进制

计算机采用的是二进制，二进制包括两个数码：\(0，1\)。

一位二进制数的可能取值有 \(2\) 个，\(k\) 位二进制数的可能取值就有 \(2^k\) 个。

在计算机中有多种数据类型，表示整数的数据类型就有好几种：

  • \(1\) 字节数，即 \(8\) 位二进制数，可能取值有 \(2^8\) 个；
  • \(2\) 字节数，即 \(16\) 位二进制数，可能取值有 \(2^{16}\) 个；
  • \(4\) 字节数，即 \(32\) 位二进制数，可能取值有 \(2^{32}\) 个；
  • \(8\) 字节数，即 \(64\) 位二进制数，可能取值有 \(2^{64}\) 个；

2、有符号整数和无符号整数

计算机中的数据类型包括有符号类型和无符号类型，有符号类型的整数称为有符号整数，无符号类型的整数称为无符号整数。

有符号整数中，最高位用于表示符号，因此最高位又称符号位。当最高位是 \(0\) 时表示 \(0\) 或正整数，当最高位是 \(1\) 时表示负整数。除了最高位以外的数位用于表示数字的大小。

无符号整数中，所有的数位都用于表示数字的大小，因此无符号整数不存在负数。

以 \(1\) 字节数为例，\(1\) 字节数包含 \(8\) 位二进制数。

对于 \(1\) 字节的有符号整数，当最高位是 \(0\) 时，\(1\) 字节数的取值范围是 \(0\) 到 \(127\)（即 \(2^7 − 1\)），当最高位是 \(1\) 时，\(1\) 字节数的取值范围是 \(−128\)（即 \(−2^7\) ）到 \(−1\)。因此 \(1\) 字节的有符号整数的取值范围是 \(−128\) 到 \(127\)，即对于有符号的 \(8\) 位二进制数，取值范围是 \(−2^7\) 到 \(2^7 − 1\)。

对于 \(1\) 字节的无符号整数，可能的最小取值是 \(0\)，最大取值是 \(255\)（即 \(2^8 − 1\)），即对于无符号的 \(8\) 位二进制数，取值范围是 \(0\) 到 \(2^8 − 1\)。

通过上述例子可以得到有符号整数和无符号整数的如下结论：

  • 有符号整数的取值范围包括负整数、零与正整数，无符号整数的取值范围只包括零与正整数，不包括负整数；
  • 在位数相同的情况下，有符号整数可以表示的最大值比无符号整数小了一半；
  • 对于 \(k\) 位整数，有符号整数的取值范围是 \(−2^{𝑘 - 1}\) 到 \(2^{k - 1} −1\)，无符号整数的取值范围是 \(0\) 到 \(2^𝑘 −1\)

3、原码、补码和反码

1）机器数和真值

在讲述原码、补码和反码的概念之前，需要先了解两个概念：机器数和真值。

一个数在计算机中的二进制表示形式称为这个数的机器数。机器数是有符号数，机器数的最高位是符号位，\(0\) 表示 \(0\) 或正数，\(1\) 表示负数。

以 \(8\) 位二进制数为例。十进制数 \(+10\) 转换成二进制数是 \(00001010\)，十进制数 \(−10\) 转换成二进制数是 \(10001010\)。这里的 \(00001010\) 和 \(10001010\) 就是机器数。

因为机器数的最高位是符号位，所以机器数的形式值不一定等于真正数值。例如 \(10001010\) 的形式值是 \(138\)，真正数值是 \(−10\)，形式值和真正数值是不同的。为了加以区分，将机器数的真正数值称为机器数的真值。

例如，\(00000010\) 的真值是 \(+2\)，\(10000010\) 的真值是 \(−2\)。

2）原码、反码和补码的概念

原码

原码是机器数的符号位加上机器数的真值的绝对值，最高位是符号位，其余位表示数值。

以 \(8\) 位二进制数为例。\(+10\) 的原码是 \(00001010\)，\(−10\) 的原码是 \(10001010\)。

\(8\) 位二进制数的原码表示的最大值是 \(01111111\)，即十进制的 \(+127\)，最小值是 \(11111111\)，即十进制的 \(−127\)，因此 \(8\) 位二进制数的原码表示的取值范围是 \(−127\) 到 \(+127\)。

原码是人脑最容易理解和计算的表示方式。

反码

反码在原码的基础上得到。

\(0\) 和正数的反码与原码相同，负数的反码是将原码的除了符号位之外的每一位取反，取反即为将 \(0\) 变成 \(1\) 或将 \(1\) 变成 \(0\)。

以 \(8\) 位二进制数为例。

  • \(+10\) 的原码是 \(00001010\)，反码是 \(00001010\)；
  • \(−10\) 的原码是 \(10001010\)，反码是 \(11110101\)。

对于负数，反码的表示方式不直观，通常需要转换成原码才能计算其数值。

补码

补码在反码的基础上得到。

\(0\) 和正数的补码与原码、反码相同，负数的补码是在反码的基础上加 \(1\) 得到。

以 \(8\) 位二进制数为例。

  • \(+10\) 的原码是 \(00001010\)，反码是 \(00001010\)，补码是 \(00001010\)；
  • \(−10\) 的原码是 \(10001010\)，反码是 \(11110101\)，补码是 \(11110110\)。

对于负数，补码的表示方式不直观，通常需要转换成原码才能计算其数值。

二、位运算符的概念和性质

1、位运算概述

计算机采用的是二进制，二进制包括两个数码：\(0,1\)。在计算机的底层，一切运算都是基于位运算实现的。

位运算共有 6 种，分别是：与、或、异或、取反、左移和右移，其中左移和右移统称移位运算，移位运算又分为算术移位和逻辑移位。上述位运算中，只有取反是一元运算，其余的都是二元运算。

2、与、或、异或和取反

  • 与运算的符号是 &，运算规则是：对于每个二进制位，当两个数对应的位都为 1 时，结果才为 1，否则结果为 0。
  • 或运算的符号是 ∣，运算规则是：对于每个二进制位，当两个数对应的位都为 0 时，结果才为 0，否则结果为 1。
  • 异或运算的符号是 ⊕（在代码中用 ^ 表示异或），运算规则是：对于每个二进制位，当两个数对应的位相同时，结果为 0，否则结果为 1。
  • 取反运算的符号是 ∼，运算规则是：对一个数的每个二进制位进行取反操作，0 变成 1，1 变成 0。

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

0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0

∼ 0 = 1
∼ 1 = 0

以下例子显示上述四种位运算符的运算结果，参与运算的数字都采用有符号的 8 位二进制表示。

46 的二进制表示是 \(00101110\)，51 的二进制表示是 \(00110011\)。考虑以下位运算的结果。

  • 46 & 51 的结果是 34，对应的二进制表示是 \(00100010\)。
  • 46 | 51 的结果是 63，对应的二进制表示是 \(00111111\)。
  • 46 ⊕ 51 的结果是 29，对应的二进制表示是 \(00011101\)。
  • ∼46 的结果是 −47，对应的二进制表示是 \(11010001\)。
  • ∼51 的结果是 −52，对应的二进制表示是 \(11001100\)。

3、移位运算

移位运算按照移位方向分类可以分成左移和右移，按照是否带符号分类可以分成算术移位和逻辑移位。

左移运算的符号是 <<。左移运算时，将全部二进制位向左移动若干位，高位丢弃，低位补 0。对于左移运算，算术移位和逻辑移位是相同的。

右移运算的符号是 >>。右移运算时，将全部二进制位向右移动若干位，低位丢弃，高位的补位由算术移位或逻辑移位决定：

  • 算术右移时，高位补最高位；
  • 逻辑右移时，高位补 0。

以下例子显示移位运算的运算结果，参与运算的数字都采用有符号的 8 位二进制表示。

  • 29 的二进制表示是 \(00011101\)。29 左移 2 位的结果是 116，对应的二进制表示是 \(01110100\)；29 左移 3 位的结果是 −24，对应的二进制表示是 \(11101000\)。
  • 50 的二进制表示是 \(00110010\)。50 右移 1 位的结果是 25，对应的二进制表示是 \(00011001\)；50 右移 2 位的结果是 12，对应的二进制表示是 \(00001100\)。对于 0 和正数，算术右移和逻辑右移的结果是相同的。
  • −50 的二进制表示是 \(11001110\)。−50 算术右移 2 位的结果是 −13，对应的二进制表示是 \(11110011\)；−50 逻辑右移 2 位的结果是 51，对应的二进制表示是 \(00110011\)。

右移运算中的算术移位和逻辑移位是不同的，计算机内部的右移运算采取的是哪一种呢？

对于 C/C++ 而言，数据类型包含有符号类型和无符号类型，其中有符号类型使用关键字 signed 声明，无符号类型使用关键字 unsigned 声明，两个关键字都不使用时，默认是有符号类型。对于有符号类型，右移运算为算术右移；对于无符号类型，右移运算为逻辑右移。

对于 Java 而言，不存在无符号类型，所有的表示整数的类型都是有符号类型，因此需要区分算术右移和逻辑右移。在 Java 中，算术右移的符号是 >>，逻辑右移的符号是 >>>。

4、移位运算与乘除法的关系

观察上面的例子可以看到，移位运算与乘除法有密切的关联性。由于计算机的底层的一切运算都是基于位运算实现的，因此使用移位运算实现乘除法的效率显著高于直接乘除法的效率。

左移运算对应乘法运算。将一个数左移 k 位，等价于将这个数乘以 \(2^k\) 。例如，29 左移 2 位的结果是 116，等价于 \(29×4\)。当乘数不是 2 的整数次幂时，可以将乘数拆成若干项 2 的整数次幂之和，例如，\(a×6\) 等价于 \((a<<2)+(a<<1)\)。对于任意整数，乘法运算都可以用左移运算实现，但是需要注意溢出的情况，例如在 8 位二进制表示下，29 左移 3 位就会出现溢出。

算术右移运算对应除法运算。将一个数右移 k 位，相当于将这个数除以 \(2^k\) 。例如，50 右移 2 位的结果是 12，等价于 \(50/4\)，结果向下取整。

从程序实现的角度，考虑程序中的整数除法，是否可以说，将一个数（算术）右移 k 位，和将这个数除以 \(2^k\) 等价？对于 0 和正数，上述说法是成立的，整数除法是向 0 取整，右移运算是向下取整，也是向 0 取整。但是对于负数，上述说法就不成立了，整数除法是向 0 取整，右移运算是向下取整，两者就不相同了。例如，\((−50)>>2\) 的结果是 −13，而 \((−50)/4\) 的结果是 −12，两者是不相等的。

因此，将一个数（算术）右移 k 位，和将这个数除以 \(2^k\) 是不等价的。

5、位运算的性质

位运算的性质有很多，此处列举位运算中的与、或、异或和取反的常见性质。假设以下出现的变量都是有符号整数。

  • 幂等律：a&a = a，a∣a = a（注意异或不满足幂等律）；
  • 交换律：a&b = b&a，a∣b = b∣a，a⊕b = b⊕a；
  • 结合律：(a&b)&c = a&(b&c)，(a∣b)∣c = a∣(b∣c)，(a⊕b)⊕c = a⊕(b⊕c)；
  • 分配律：(a&b)∣c = (a∣c)&(b∣c)，(a∣b)&c = (a&c)∣(b&c)，(a⊕b)&c = (a&c)⊕(b&c)；
  • 德·摩根律：∼(a&b) = (∼a)∣(∼b)，∼(a∣b) = (∼a)&(∼b)；
  • 取反运算性质：−a = ∼(a−1)；
  • 与运算性质：a&0 = 0，a&(−1) = a，a&(∼a) = 0；
  • 或运算性质：a∣0 = a，a∣(∼a) = −1；
  • 异或运算性质：a⊕0 = a，a⊕a = 0；
  • 其他性质：
    • a&(a−1) 的结果为将 a 的二进制表示的最后一个 1 变成 0；
    • a&(−a)（与 a&(∼(a−1)) 等价）的结果为只保留 a 的二进制表示的最后一个 1，其余的 1 都变成 0。

利用上述性质，可以巧妙地解决很多位运算的题目。

三、例题