数字在计算机中的表示

真值

真值因为机器数第一位是符号位，所以机器数的形式值不等于真正的数值。例如上面的有符号数1000 0011，其最高位1代表负，其真正数值是-3而不是形式值131（1000 0011转换为十进制等于131）。所以将带符号位的机器数对应的真正数值称为机器数的真值。例：0000 0001的真值 = +000 0001 = +1，1000 0001的真值 = -000 0001 = -1

原码

原码就是符号位加上真值的绝对值，即用第一位表示符号，其余位表示值，比如如果是8位二进制：

1
2

[+1]原 = 0000 0001
[-1]原 = 1000 0001

第一位是符号位，因为第一位是符号位，所以8位二进制数的取值范围就是：
[1111 1111，0111 1111]，也即[-127，127]

反码

反码的表示方式是：正数的反码是其本身，而负数的反码是在其原码基础上，符号位不变，其余各个位取反。
例如：

1
2

[+1]原 = [0000 0001] 原 = [00000001]反
[-1]原 = [1000 0001] 原 = [11111110]反

可见如果一个反码表示的是负数，人脑无法直观的看出来它的数值，通常要将其转换成原码再计算。

补码

在应用中，因为补码能保持加和减运算的统一，因此应用更广，其表示方式是：

• 正数的补码就是其本身；
• 负数的补码是在其原码的基础上，符号位不变，其余各个位取反，最后 + 1 (即在反码的基础上+1)

  1 2	[+1]原 = [0000 0001] 原 = [00000001]反 = [00000001] 补 [-1]原 = [1000 0001] 原 = [11111110]反 = [11111111] 补

  对于负数，补码表示方式也是人脑无法直观看出来其数值的，通常也需要转换成原码再计算其数值。

拓展：为何会有原码，补码，反码

既然原码能表示数据，为什么实际软件中更多使用的是补码呢？
现在我们知道了计算机有三种编码方式来表示一个数，编码结果如下：

1
2

[+1]原 = [0000 0001] 原 = [00000001]反 = [00000001] 补
[-1]原 = [1000 0001] 原 = [11111110]反 = [11111111] 补

可以发现原码，反码和补码是完全不同的。既然原码才是被人脑直接识别并用于计算表示方式，为何还会有反码和补码呢？
首先，因为人脑可以知道第一位是符号位，在计算的时候我们会根据符号位选择对真值区域的加减。但是计算机要辨别”符号位”就必须获得全部的位的数据才可以，如果是一个32位甚至64位的以系统， 显然会让计算机的基础电路设计变得十分复杂！ 于是人们想能否将符号位也参与运算的方法。
我们知道， 根据运算法则减去一个正数等于加上一个负数， 即: 1-1 = 1 + (-1) = 0，所以机器可以只有加法而没有减法，这样计算机运算的设计就更简单了。于是人们开始探索将符号位参与运算，并且只保留加法的方法。
看个例子，计算十进制表达式：1-1=0，首先看原码表示：
1 - 1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原 = [1000 0010]原 = -2
如果用原码表示，让符号位也参与计算，显然对于减法来说，结果是不正确的，这也是为何计算机内部不使用原码表示一个数。
为了解决原码做减法的问题就出现了反码，此时计算十进制的表达式为：1 - 1 = 0

1
2
3
4
5

1 - 1 = 1 + (-1)
= [0000 0001]原 + [1000 0001]原
= [0000 0001]反 + [1111 1110]反
= [1111 1111]反 = [1000 0000]原
= -0

可以看到用反码计算减法结果的真值部分是正确的，但是“0”的表示有些奇怪

注意⚠️：取反和反码是不一样的

• 取反不区分符号位，全部位取反；
• 反码区分符号位，符号位不变，其余位取反。
  

位运算的规则

移位运算

移位运算按照移位方向分类可以分成左移和右移，按照是否带符号分类可以分成算数移位和逻辑移位。
原始： 0000 0110 [6]
右移一次： 0000 0011 [3] 相当于除2
左移一次： 0000 1100 [12] 相当于乘2

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

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

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

• 示例1: 29的二进制表示是0001 1101。29左移2位的结果时116，对应二进制 0111 0100；29左移3位的结果是 -24，对应的二进制是1110 1000
• 示例2: 50的二进制表示是0011 0010。50右移一位的结果是25，对应的二进制表示是 0001 1001；50右移2位的结果是12，对应的二进制表示是0000 1100。对于0和正数，算数右移和逻辑右移的结果是相同的。
• 示例3:-50的二进制表示是 11001110（补码）。-50算术右移2位的结果是-13，对应的二进制表示是1111 0011；-50逻辑右移2位的结果是51，对应的二进制表示是00110011。

计算机内部的右移运算采取的是哪一种呢？

• 对于C/C++而言，数据类型包含有符号类型和无符号类型，其中有符号类型使用关键字signed声明，无符号类型使用关键字unsigned声明，两个关键字都不使用时，默认是有符号类型。对于有符号类型，右移运算位算术右移；对于无符号类型，右移运算为逻辑右移。
• 对于Java而言，不存在无符号类型，所有的表示整数的类型都是有符号类型，因此需要区分算数右移和逻辑右移。在Java中，算数右移的符号是 >>，逻辑右移的符号是>>>。

位运算常用技巧

获取

该方法将1左移i位，得到形如 0001 0000的值。接着对这个值与num执行“位与”操作，从而将i位之外的所有位清零，最后检查该结果是否为零。不为零说明i位为1，否则i位为0。

1
2
3
4
5

boolean getBit(int num, int i) {
    // 除了i位全变为0
    // 检查num的i位是否为0
	return ((num & (1 << i) != 0);
}

设置（将某一位设置为1）

setBit先将1左移i为，得到形如 0001 0000的值。接着对这个值与num执行“位或”操作，这样只会改变i位的数据。
这样除i位外的位均为0，故不会影响num的其余位。代码如下：

1
2
3

boolean setBit(int num, int i) {
    return num | (1 << i);
}

清零（将某一位设置为0）

该方法与setBit相反，首先将1左移i位获得形如 0001 0000的值，对这个值取反进而得到类似1110 1111的值，接着对该值和num执行“位与”，故而不会影响到num的其余位，只会清零i位。

1
2
3
4
5

int clearBit(int num, int i) {
    //取反
    int mask = ~(1 << i);
    return num & mask;
}

更新

这个方法是将setBit和clearBit合二为一，首先用诸如1110 1111的值将num的第i位清零。接着将待写入值v左移i位，得到一个i位为v但是其余位都为0的数。最后对之前的结果执行“位或”操作，v为1这num的i位更新为1，否则为0

1
2
3
4
5

int clearBit(int num, int i, int v) {
    //取反
    int mask = ~(1 << i);
    return (num & mask) | (v << i);
}

LeetCode371 位运算实现加法

给你两个整数 a 和 b ，**不使用 **运算符 + 和 - ，计算并返回两整数之和。
示例 1：

1
2

输入：a = 1, b = 2
输出：3

示例 2：

1
2

输入：a = 2, b = 3
输出：5

两个二进制位相加的情况：

1
2
3
4

[1] 0 + 0 = 0
[2] 1 + 0 = 1
[3] 0 + 1 = 1
[4] 1 + 1 = 0 (进位)

两数相加考虑的情况有两种 1. 进位部分 2. 不进位部分
不进位：
a 和 b 两个数不进位部分的情况是：相同为0，不同为1，这就是 a ^ b
进位：
对于进位，只有a和b均为1的时候才会进位，并且进位只能是1，可以想到 a & b = 1，此时位数向前进1
也就是 (a & b) << 1

思路：将a和b的和，拆分为a和b的无进位加法结果与进位结果的和
代码如下：

1
2
3
4
5
6
7
8
9
10

public int getSum(int a, int b) {

    while (b != 0) {
        int sign = (a & b) << 1;
        //第一次循环的时候，就把a看作不进位的数，b看作进位的数
        a = a ^ b;
        b = sign;
    }
    return a;
}

图解：

LeetCode面试08.05 递归乘法

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
示例1:

1
2

输入：A = 1, B = 10
 输出：10

示例2:

1
2

输入：A = 3, B = 4
 输出：12

思路：首先，求得A和B的最小值和最大值，对其中的最小值当作乘数（为什么选最小值，因为选最小值当乘数，可以算的少），将其拆分成2的幂的和。其实就是用二进制的视角去看待最小值min，比如12用二进制表示就是1100，即1000 + 0100。例如：
13 * 12 = 13 * (8 + 4)= 13 * 8(1000) + 13 * 4(0100) = (13 << 3) + (13 << 2);

1
2
3
4
5
6
7
8
9
10
11
12
13

public int multiply(int A, int B) {
    int min = Math.min(A,B);
    int max = Math.max(A,B);
    int ans = 0;
    while (min != 0) {
        if ((min & 1) == 1) {
            ans += max;
        }
        min >>= 1;
        max += max;
    }
    return ans;
}

难点解读：
max的值变化并不是 13 -> 26 -> 39…这样变化的
max的值：13 -> 26 -> 52 -> 104
每次max 都会加自己本身的值实现一个递归
进而max的变化和2进制是一样的

13 * 8(1000) + 13 * 4(0100)
最后一位为0时 逻辑就是min >> 1， max 左移一位 (相当于加倍)。

哪些开源软件用到了位运算

位运算在计算机科学和软件开发中的许多场景中都得到了广泛应用。以下是一些常见的开源软件和场景，其中使用了位运算：

1. Linux内核：
   • 位运算在Linux内核中用于处理权限、掩码和位掩码等方面，以及在底层硬件通信中的一些操作。
2. 网络编程：
   • 位运算在网络编程中经常用于处理IP地址、子网掩码和端口等信息，例如在计算机网络协议的解析和构建中。
3. 数据库系统：
   • 在一些数据库系统的底层实现中，位运算可用于位图索引、权限管理和数据压缩等方面。
4. 图形处理和游戏开发：
   • 位运算在图形处理和游戏开发中用于处理像素操作、掩码处理以及一些图形算法，如图像旋转和平移等。
5. 密码学和安全性：
   • 位运算在密码学中用于实现加密算法，例如位移操作在一些简单的加密算法中被广泛使用。
6. 数据结构：
   • 位运算在一些数据结构的实现中，如位向量、位图、布隆过滤器等，用于高效地表示和操作大量的布尔值。
7. 嵌入式系统和驱动开发：
   • 在嵌入式系统和驱动开发中，位运算用于对寄存器进行位操作，配置硬件参数和执行底层控制。
8. 算法和优化：
   • 位运算在一些算法和优化技巧中被广泛应用，例如在位操作中实现快速乘法、快速除法，或者对整数进行快速的取模和取余操作。

这只是一小部分的例子，位运算在计算机科学的各个领域都有着重要的应用。在开源软件的代码中，你可能会在这些场景中找到位运算的使用。

位元算应用场景

在不同的场景中，位运算可以执行各种不同的操作。以下是一些常见的位运算操作，它们在上述提到的场景中可能被用到：

1. 位掩码（Bitmasking）：
   • 通过位运算，可以使用位掩码来提取、设置或清除特定的位，从而进行一些标志位的管理。例如，通过位与运算（&）和位或运算（|）来设置和清除特定的标志位。
2. 权限管理：
   • 在权限管理中，位运算可以用于将不同的权限值进行组合。每个权限可以使用一个位表示，然后通过位运算来合并或检查用户的权限。
3. 网络编程中的IP地址操作：
   • IP地址和子网掩码通常以32位整数表示。通过位运算，可以进行IP地址的分割、合并以及与子网掩码的按位与运算，以确定网络地址。
4. 图形处理：
   • 位运算可用于图形处理，例如通过位与运算来创建掩码，将两个图像进行合并或提取特定部分。
5. 加密算法：
   • 在密码学中，位运算常用于实现加密算法，例如通过位异或运算（^）进行简单的异或加密。
6. 数据结构中的位图和位向量：
   • 位运算在位图和位向量的操作中非常常见，用于高效地表示和处理大量的布尔值。
7. 嵌入式系统和驱动开发中的寄存器操作：
   • 在嵌入式系统和驱动开发中，位运算常用于对硬件寄存器进行位操作，配置设备参数和执行底层控制。
8. 算法中的位操作：
   • 在算法中，位运算可用于一些优化技巧，如通过位移操作实现快速乘法和除法。

总的来说，位运算在这些场景中主要用于高效地进行二进制位的处理，执行一些特定的位级操作，以满足程序的需求并提高性能。