Odyssey Technology

Appearance

位运算 ​

位运算符 & | >> << ​

  • 与运算：&

    • 10010110 & 00000111 => 00000110
    • 都为1时为1，否则为0
    • a & b 取某些“共同为 1”的位 (num & 0x7f 取低7位)

  • 或运算：|

    • 10010110 | 00011111 => 10011111
    • 只要一个为1时为1，就为1
    • a | b 把某些位打开，比如权限位、标记位，经常这么干（(num & 0x7f) | 0x80）

  • 左移运算：<<

    • 10010110 << 4 => 10110000
    • 向左移动四位，相当于乘以2**4
      • x << 1 ≈ x * 2
      • x << 2 ≈ x * 4
      • x << 3 ≈ x * 8
      • x << 4 ≈ x * 16
    • num << 1 快速乘 2

  • 右移运算：>>

    • 10010110 >> 4 => 00001001
    • 向右移动四位，相当于除以2**4
      • x >> 1 ≈ x / 2
      • x >> 2 ≈ x / 4
      • x >> 3 ≈ x / 8
      • x >> 4 ≈ x / 16
    • num >> 1 快速除 2

  • >>> 是无符号右移

  • <<< js 中没有这个运算符

>> 与 >>> 的区别 ​

  • >> 是有符号右移

    • 整体往右移
    • 左边空出来的位，用“符号位”补
    • 正数补 0
    • 负数补 1

  • >>> 是无符号右移

    • 也是整体往右移
    • 但左边空出来的位，永远补 0
    • 不管原来是正数还是负数

  • 正数：>> 与 >>> 结果相同

    • 10 >> 1 // 5
    • 10 >>> 1 // 5
    • 00001010 右移1位 => 00000101 // 5

  • 负数：>> 与 >>> 结果不同

    • -8 >> 1 // -4
    • -8 补码 => 11111111 11111111 11111111 11111000 >> 1 => 11111111 11111111 11111111 11111100 // -4
    • -8 >>> 1 // 2147483644
    • -8 补码 => 11111111 11111111 11111111 11111000 >>> 1 => 01111111 11111111 11111111 11111100 // 2147483644

>> 有符号右移，保留负号倾向 >>> 无符号右移，强行当成无符号整数处理

源码、反码、补码 ​

  • 原码、反码和补码是计算机中表示数字的不同编码方式，主要用于解决带符号整数的表示和运算问题。

1. 机器数和真值 ​

  • 机器数: 数字在计算机中的二进制表示形式，带有符号位。例如，用8位二进制表示+3是00000011，-3是10000011。这里的00000011和10000011就是机器数
  • 真值: 机器数真正代表的数值。因为机器数包含符号位，所以其形式值不等于真正的数值。例如，10000011的真值是-3，而不是131

2. 原码 ​

  • 定义:
    • 原码是最直观的表示方式，符号位加上真值的绝对值。
    • 如果是8位二进制，第一位表示符号，后面7位表示数值。
    • 正数的原码符号位为0，负数的原码符号位为1。
  • 例如：
    • [+1] = [0000 0001]<sub>原</sub>
    • [-1] = [1000 0001]<sub>原</sub>
  • 范围: 8位二进制原码的表示范围是[-127, +127]。
  • 优点: 简单直观，易于理解。
  • 缺点:
    • 原码不能直接参与运算，因为符号位需要单独处理。例如，1 + (-1) = 0，但是用原码计算 00000001 + 10000001 = 10000010，结果为 -2，显然是错误的。
    • 零的表示不唯一，[+0]和[-0]的原码分别为0000 0000和1000 0000。

3. 反码 ​

  • 定义:
    • 正数的反码与其原码相同。
    • 负数的反码是在其原码的基础上，符号位不变，其余各位取反。
  • 例如：
    • [+1] = [00000001]<sub>原</sub> = [00000001]<sub>反</sub>
    • [-1] = [10000001]<sub>原</sub> = [11111110]<sub>反</sub>
  • 作用: 作为原码到补码的过渡码。
  • 缺点:
    • 反码表示负数时，人脑无法直观地看出其数值，通常需要转换成原码再计算。
    • 零的表示仍然不唯一。

4. 补码 ​

  • 定义:
    • 正数的补码与其原码相同。
    • 负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后+1（即在反码的基础上+1）。
  • 例如：
    • [+1] = [00000001]<sub>原</sub> = [00000001]<sub>反</sub> = [00000001]<sub>补</sub>
    • [-1] = [10000001]<sub>原</sub> = [11111110]<sub>反</sub> = [11111111]<sub>补</sub>
  • 关键特性:
    • 解决了零的表示不唯一的问题: 补码中，零只有一种表示方式（0000 0000）。
  • 可以将减法运算转换为加法运算: 计算机可以只保留加法而没有减法，简化了计算机运算的设计。
  • 扩展了负数的表示范围: 使用补码，8位二进制可以表示的范围是[-128, 127]，其中[1000 0000]<sub>补</sub>表示-128，但-128没有原码和反码表示。
  • 运算: 补码运算下，符号位可以参与运算，结果仍然正确。
  • 总结
    • 原码：最简单的表示形式，但不能直接用于计算。
    • 反码：是求补码的过渡形式。
    • 补码：最常用的表示形式，解决了原码的诸多问题，便于计算机进行加减运算。
    • 简而言之，补码通过将减法转换为加法，并统一了零的表示，极大地简化了计算机的运算逻辑。

补码 ​

为什么负数用补码表示 ​

  • 如果用源码就会出问题，因为加法电路不好统一处理
    js
    +1 = 00000001
-1 = 10000001

1 + (-1)

00000001
10000001
--------
10000010
  • 补码解决了什么问题：把减法问题，统一成加法问题
    • a - b => a + (-b) => a + b的补码
    • 而 -b 用补码表示后，硬件只需要一套加法器就能算。
  • 第三，符号和数值计算能自然衔接

补码好处 ​

  • 第一，0 只有一种表示
  • 第二，加减法能统一
  • 第三，补码下，整数的溢出、加法、减法、移位，都能在统一规则里处理。

位运算不是在操作“数学上的负号”，而是在操作这个数在内存里的二进制表示。

而负数在内存里的二进制表示，就是补码。

你可以把“补码”理解成：计算机为负数发明的一套编码规则。

补码是如何算对的 ​

  • 因为补码把“负数”设计成了一种能和普通二进制加法兼容的编码。

  • 这样硬件根本不用专门理解“负号”，只要按普通加法做，结果就对了。

  • 1 + (-1) = 0

  • 1 的补码 => 00000001

  • -1 的补码 => 11111111

  • 00000001 + 11111111 = 100000000

  • 8 位寄存器，最高位那个进位 1 丢掉，结果为 00000000

补码的本质 ​

  • 固定宽度的环
    • 计算机的整数位数是固定的，比如 8 位、32 位
    • 本质上是在一个“固定宽度的环”里算数
    • 8 位能表示的总状态数是：2^8 = 256
    • 它的运算本质上是：对 256 取模
    • 256 ≡ 0
    • 00000000 => 其实对应十进制 256
    • 但在 8 位里，256 会回绕成：0
    • 固定字长整数运算的自然规则
  • 回绕
    • 补码其实是在利用“回绕”
    • 补码不是在说：-1 真的是 11111111
    • 而是我们规定：11111111 这个位模式，解释成 -1
    • 因为这样一来，它和正数相加时，会借助“溢出回绕”自动得到正确结果。
    • 想象一个只有 1 位十进制的钟表，只能显示：0,1,2,3,4,5,6,7,8,9，它是“模 10”系统。
    • 0 - 1 => 0 + 9 = 9 因为 9 就相当于 “-1 mod 10”
    • 在模 10 里，9 可以扮演 -1 的角色
    • 同理，在 8 位二进制（模 256）里：255 = 11111111 就扮演了 -1 的角色
    • 因为：1 + 255 = 256 ≡ 0 (mod 256) 所以：11111111 被定义成 -1，是完全合理的
  • 数学本质
    • 对于 n 位整数，补码实际上是在做这件事：
    • 把负数 -x 编码成 2^n - x
    • -1 => 2^8 - 1 = 255 = 11111111
    • -2 => 2^8 - 2 = 254 = 11111110
    • 这就是为什么“取反加 1”能得到补码。
    • 因为：2^n - x = (~x) + 1 在固定 n 位下，这两种写法是等价的。
  • a + (-b)
    • 如果 -b 用补码表示，其实就是：a + (2^n - b)
    • 在 n 位系统里，超过 2^n 的部分会自动丢弃，所以结果相当于：a - b
    • 这就是补码统一加减法的根本原因。
  • 硬件
    • 硬件最怕分两套规则
    • 减法不用真的设计“减法器”，只要把减数变成补码，再丢给加法器。
    • 所以从硬件角度看，补码不是“编码好看”，而是：它让电路极大简化。

位运算符 ^ ~ ​

  • ^：异或，不同为 1，相同为 0
    js
    - 0 ^ 0 = 0
- 1 ^ 1 = 0
- 0 ^ 1 = 1
- 1 ^ 0 = 1
    js
    5 = 0101
3 = 0011
---------
^ = 0110
    • ① 翻转某一位
      • 如果那一位原来是 1，再异或 1，又会变成 0
    • ② 相同的数异或等于 0
      • 5 ^ 5 // 0
      • a ^ a = 0
      • a ^ 0 = a
      • a ^ b ^ b = a
  • ~：按位取反，0 变 1，1 变 0
    • ~x = -(x + 1)
    js
    5  = 00000101
~5 = 11111010
00000000 00000000 00000000 00000101
11111111 11111111 11111111 11111010 => -6