AG2 二进制和位运算

· 更新于 2026/8/27· Tech

算法位运算

1. 机器数的表示

计算机内部以二进制存储数据。为了理清位运算的用法，需要先理解计算机中数据的编码。

1.1 编码

个人认为二进制是最简单、最自然的数据表示法，因为它通过 0 和 1 直接表达信息的有和无这两种状态。翻开任意一本计算机科学相关的书，我们都可以得知计算机中的数据表示方法包括原码、反码和补码。下面简要介绍这些编码方法。

原码是最简单的表示法，因为它的出发点就是为了直观的表示正数和负数。

  • 使用最高有效位（MSB）作为符号位，当为 Big-endian 时是最左侧那位（最高位）
  • 其余位表达数值的绝对值

例如，1 字节可以表达的范围：首位为符号 0 / 1，其余 7 位可以表达 0 ~ 127，所以这样的编码可以表示 −127- 127 ~ +127+ 127 的范围。

编码是服务计算机的，因此必须便于计算。从这个角度出发，原码并不够格。

它的主要缺陷有二：

  1. 符号位无法直接参与计算，需要为加法和减法各自设计一套硬件电路
    • 加法需要进位电路
    • 减法需要借位电路
    • 条件判断电路...
  2. 零的表示不唯一
    • 0000 0000 和 1000 0000

为了降低硬件运算的成本，并且提高运算速度，需要提出一种适于计算的编码方式。

反码这种编码方式，在一定程度上降低了硬件计算的复杂度。

反码又称为 ones' complement （译为一补数？），它将一个负数的二进制形式表示为其对应的正数原码的逐位反转。例如 5 表示为 0000 0101，-5 表示为 1111 1010。

反码通过补数法的理念，简化加法与减法的运算。先拿十进制数举例，计算

253−176= ?253 - 176 = ~?

上述减法正常来说需要借位，我们将其变化为下式

253+(999−176)+(1−1000)= ?253 + (999 - 176) + (1 - 1000) = ~?

  • 式 999−176999 - 176 得到 176 的 nines' complement （译为九补数？），即 823823
  • 计算式 253+823253 + 823，即 10761076
  • 上式产生了进位，将最高位的 1 去掉，并且加回最低位 ，即 7777

将上述过程炮制到二进制运算中，就可以将减法转换加法，从而简化运算电路。注意上述过程最后一步，它是通过循环进位和硬件溢位实现的。

反码通过将负数表示为 ones' complement，把减法转换为加法。当计算结果遇到溢位时，将溢位加到最低位即可。

优点：

  • 简化硬件电路，不再需要区分加减法，改成取反器

缺点：

  • 引入循环进位，需要电路实现
  • 零的表示还是不唯一
    • 0000 0000 和 1111 1111

数学的实数域是无限的，而电脑只能处理有限的位数。为在有限编码上实现自圆其说地正确的运算，我们只好在有限域上做加法后，再做模除（modulo）把结果控制在有限范围。

补码正是基于上述思想诞生的，它解决了反码和原码的一部分缺点。

补码又称为 two's complement（译为二补数？ 需要注意这里的 two 不是复数形式，跟之前术语的英文有区别），它借助模算术配合二进制，避开了反码中的循环进位以及零的表示不唯一的缺陷。

P.S. 个人思考

反码和补码本质都借助了模运算的思想（它们都使用补数法）。

  • 反码：模 2n−12^n - 1
  • 补码：模 2n2^n

但是补码选择模数在二进制下是更合理的。假设用 4 位表示机器数：

  • 在反码的模数下，0000 和 1111 同余，那么会产生两种零的表示
  • 在补码的模数下，0000 和 10000 同余，这样可以通过二进制下的进位与溢出，使得零的表示唯一

补码表示的最大正数和最小负数并不对称，也可以用这个视角解释（因为 0 的编码唯一了，对于 4 位二进制数共 16 种编码，分给正数和负数的编码为 15 种。因而 4 位有符号数的范围为 -8 ~ +7，这样的编码方式比原码和反码利用更充分，没有造成浪费）。

  • 正数的补码和原码相同
  • 负数的补码是其反码加 1 （推导见下）

设有效位数为 kk，那么
A+¬A=2k−1A + \neg A = 2^k - 1
于是
A+(¬A+1)≡2k≡0(mod2k)A + (\neg A + 1) \equiv 2^k \equiv 0 \pmod{2^k}
因为 −A−A 是 AA 的反元素（相加为 0），故：
−A:=¬A+1-A := \neg A + 1

例如，+5 表示为 0000 0101 ，-5 表示为 1111 1011。

对于补码的阅读，常见做法是读权数（参见 CSAPP 的讲解）：

  • 0000 0101 是正数，直接读为 22+20=4+1=52^2 + 2^0 = 4 + 1 = 5
  • 1111 1011 是负数，即 1011 ，最高位贡献负权值，其余低位贡献正权值
    因此读为 −23+21+20=−8+2+1=−5- 2^3 + 2^1 + 2^0 = -8 + 2 + 1 = -5

现代计算机内部广泛使用补码表示有符号整数，因为它简化了硬件设计和运算处理。

优点：

  • 避免循环进位，一个加法器解决加减法
    做减法时输入反码并加 1 即可

缺点：

  • 范围不对称，可读性较差，有溢出风险

1.2 解释

1.1 中只解释了如何编码，但是最终解释权归计算机。同一种二进制形式，可以有不同的表达含义。例如，有符号整数和无符号整数在机器中的表示：

4 位有符号数的范围为 -8 ~ +7，4 位无符号数的范围为 0 ~ 15 。

2. 位运算

以下是六种基本的位运算：

  • &：按位与
  • |：按位或
  • ^：按位异或
  • ~：按位取反
  • <<：左移
  • >>：右移

主要需要注意：

  • 按位异或运算符 ^ ，它的逆运算是其本身，即两次异或同一个数之后结果不变：

a⊕b⊕b=aa \oplus b \oplus b = a

  • 移位运算中若出现以下情况，则其行为未定义（以 int 为例）：

    • 移位数为负数，如 a << -1
    • 移位数大于等于左操作数的位数 a << 32

  • 右移操作

    • 算术右移：左边会补上对应的符号位
    • 逻辑右移：左边一律补零

3. 技巧

3.1 符号与基础

  1. 消去整数 x 二进制表示中最右侧的那个 1

通过 x & (x - 1) ，可以消去 x 最后一位中的那个 1。

可以将整数 x 划分成两个部分

  • 一部分为高位 x_high
  • 一部分为最右侧的 1 以及其后部分（形如 100...0）

那么，x 和 x - 1 就可以表示为：

  • x 的二进制表示：x_high 100...0
  • x - 1 的二进制表示：x_high 011...1

于是，对二者进行按位与，就可以得到 x_high 000...0。

e.g.e.g. 此方法对所有整数都生效，下面举一个负数的例子，例如 x 为 -8：

x 的二进制表示：1111 1000
x - 1 的二进制表示：1111 0111

x & (x - 1) = (1111 0000)

参考练习：

参考

  1. 解讀計算機編碼

    https://hackmd.io/@sysprog/binary-representation

  2. 原码、反码、补码 | 菜鸟教程

    https://www.runoob.com/w3cnote/sign-magnitude.html

  3. Bit Operations - OI Wiki

    https://en.oi-wiki.org/math/bit/

  4. Bit Twiddling Hacks

    https://graphics.stanford.edu/~seander/bithacks.html

cicada@blog:~
$ cat series/prev→AG1 时间复杂度
$ grep related→LC191 - 位 1 的个数2026/08/27→LC231 - 2 的幂2026/08/26

本作品采用 CC BY-NC-SA 4.0 许可协议

转载或引用请注明出处