二进制与位运算

1. 二进制的基本概念

1.1 什么是二进制？

二进制是计算机世界的基础语言，与我们日常使用的十进制不同，它只使用两个数字符号：0和1。

十进制：使用0-9这十个数字符号
二进制：只使用0和1两个数字符号

计算机内部所有的数据处理和存储都是基于二进制的，因为电子元件的特性决定了它们最容易表示和处理两种状态（开/关、有电/无电）。

1.2 二进制与十进制的对比

二进制和十进制的原理其实是相似的：

十进制：每个位置的权重是10的幂（1, 10, 100, 1000...）
二进制：每个位置的权重是2的幂（1, 2, 4, 8, 16, 32...）

例如，十进制数字123的含义是：

1×100 + 2×10 + 3×1 = 123

而二进制数字1011的含义是：

1×8 + 0×4 + 1×2 + 1×1 = 11(十进制)

1.3 二进制转十进制示例

将二进制数1001110转换为十进制：

1×64 + 0×32 + 0×16 + 1×8 + 1×4 + 1×2 + 0×1
= 64 + 0 + 0 + 8 + 4 + 2 + 0
= 78

2. 原码、反码和补码

2.1 为什么需要原码、反码和补码？

在计算机中表示数字（尤其是负数）时，我们需要一种简单高效的方式。原码、反码和补码就是为此设计的三种表示形式，其中补码是计算机中最常用的表示形式。

2.2 原码 (True Form)

原码是最简单直观的二进制表示法： - 最高位作为符号位（0表示正数，1表示负数） - 其余位表示数值的绝对值

例如： - +5 的原码：00000101 - -5 的原码：10000101

2.3 反码 (One's Complement)

反码的表示方法： - 正数的反码与原码相同 - 负数的反码是其原码除符号位外，其余各位取反（0变1，1变0）

例如： - +5 的反码：00000101 (与原码相同) - -5 的反码：11111010 (符号位为1，其余位取反)

2.4 补码 (Two's Complement)

补码的表示方法： - 正数的补码与原码相同 - 负数的补码是其反码加1

例如： - +5 的补码：00000101 (与原码相同) - -5 的补码：11111011 (反码11111010加1)

2.5 为什么计算机使用补码？

计算机使用补码表示负数有几个重要原因：

统一的加法规则：使用补码可以用同一套电路处理正数和负数的加法，无需区分符号
避免零的双重表示：在原码和反码中，+0和-0有不同表示（+0: 00000000, -0: 10000000），而在补码中，0只有一种表示（00000000）
简化硬件设计：补码运算可以简化计算机硬件设计，提高效率

2.6 三种码制的转换关系

对于任何整数： - 正数：原码 = 反码 = 补码 - 负数：补码 = 反码 + 1 = 原码符号位不变，其余位取反 + 1

2.7 实例演示

让我们以数字-15为例，演示三种码制的转换过程：

-15的原码：
符号位为1，其余位是15的二进制表示
15的二进制是1111
所以-15的原码是：10001111（8位表示）
-15的反码：
符号位保持不变，其余位取反
原码：10001111
取反后：11110000
-15的补码：
反码加1
反码：11110000
加1后：11110001

所以在计算机中，-15通常以补码形式11110001存储。

3. 负数的二进制表示

3.1 符号位概念

在计算机中，二进制数的最高位通常被用作符号位： - 0：表示正数 - 1：表示负数

3.2 负数的表示方法：取反加一

计算机使用"补码"表示负数，具体步骤是： 1. 取该数的正值的二进制表示 2. 对所有位取反（0变1，1变0） 3. 在结果上加1

例如，计算-5的二进制表示： 1. 5的二进制是：00000101 2. 取反：11111010 3. 加1：11111011

所以-5的二进制表示是：11111011

3.3 负数的识别与转换

如何从二进制判断一个数是正数还是负数？ - 看最高位：如果是0，则为正数；如果是1，则为负数

如何将负数的二进制转换为十进制？ 1. 先判断最高位是否为1 2. 如果是1，说明是负数，则进行取反加一的逆操作 3. 取反后加一，得到正值 4. 加上负号

4. 位运算基础

4.1 基本位运算

位运算是直接对二进制位进行操作的运算，主要包括：

与运算(&)

规则：两个位都为1时，结果才为1；否则为0
示例：
```
1010 & 1100 = 1000
```

或运算(|)

规则：两个位只要有一个为1，结果就为1；两个都为0才为0
示例：
```
1010 | 1100 = 1110
```

异或运算(^)

规则：两个位相同时为0，不同时为1
示例：
```
1010 ^ 1100 = 0110
```

取反运算(~)

规则：0变1，1变0

示例：

~1010 = 0101（简化示例，实际计算机中会处理所有位）

4.2 位运算示例代码


#include <iostream>
using namespace std;

int main() {
    int a = 10;  // 二进制：1010
    int b = 12;  // 二进制：1100

    cout << "a & b = " << (a & b) << endl;  // 输出: 8 (1000)
    cout << "a | b = " << (a | b) << endl;  // 输出: 14 (1110)
    cout << "a ^ b = " << (a ^ b) << endl;  // 输出: 6 (0110)
    cout << "~a = " << (~a) << endl;        // 输出取决于整数表示

    return 0;
}

5. 移位运算

5.1 左移运算(<<)

左移运算将二进制数的所有位向左移动指定的位数，右边补0。

效果：每左移一位，相当于乘以2

示例：

5 << 1 = 10  (二进制: 101 -> 1010)
5 << 2 = 20  (二进制: 101 -> 10100)

5.2 右移运算(>>)

右移运算将二进制数的所有位向右移动指定的位数。

效果：每右移一位，相当于除以2

示例：

10 >> 1 = 5  (二进制: 1010 -> 101)
10 >> 2 = 2  (二进制: 1010 -> 10)

5.3 移位运算示例代码

#include <iostream>
using namespace std;

int main() {
    int a = 5;  // 二进制: 101

    cout << "a << 1 = " << (a << 1) << endl;  // 输出: 10
    cout << "a << 2 = " << (a << 2) << endl;  // 输出: 20

    int b = 10;  // 二进制: 1010

    cout << "b >> 1 = " << (b >> 1) << endl;  // 输出: 5
    cout << "b >> 2 = " << (b >> 2) << endl;  // 输出: 2

    return 0;
}

6. 二进制加法

6.1 二进制加法基本规则

二进制加法的规则很简单： - 0 + 0 = 0 - 0 + 1 = 1 - 1 + 0 = 1 - 1 + 1 = 10 (需要进位，当前位为0，向高位进1)

6.2 二进制加法示例

计算 3 + 5 的二进制加法过程：

  0011 (3)
+ 0101 (5)
------
  1000 (8)

解析： - 个位：1+1=10，当前位为0，进位1 - 十位：1+0+1(进位)=10，当前位为0，进位1 - 百位：0+1+1(进位)=10，当前位为0，进位1 - 千位：0+0+1(进位)=1，当前位为1

7. 位运算的应用

操作说明	输入 (10进制)	输入 (2进制)	操作表达式
去掉最后一位	10 → 5	1010 → 101	`x >> 1`
在最后加一个0	5 → 10	101 → 1010	`x << 1`
在最后加一个1	5 → 11	101 → 1011	`(x << 1) + 1`
把最后一位变成1	12 → 13	1100 → 1101	`x \| 1`
把最后一位变成0	15 → 14	1111 → 1110	`(x \| 1) - 1`
最后一位取反	12 → 13	1100 → 1101	`x ^ 1`
把右数第k位变成1	12 → 14, k=2	1100 → 1110	`x \| (1 << (k - 1))`
把右数第k位变成0	12 → 8, k=3	1100 → 1000	`x & ~(1 << (k - 1))`
右数第k位取反	14 → 12, k=2	1110 → 1100	`x ^ (1 << (k - 1))`
取末三位	21 → 5	10101 → 101	`x & 7`
取末k位	11 → 3, k=2	1011 → 11	`x & ((1 << k) - 1)`
取右数第k位	11 → 1, k=4	1011 → 1	`(x >> (k - 1)) & 1`
把末k位变成1	8 → 15, k=3	1000 → 1111	`x \| ((1 << k) - 1)`
末k位取反	16 → 23, k=3	10000 → 10111	`x ^ ((1 << k) - 1)`
把右边连续的1变成0	11 → 8	1011 → 1000	`x & (x + 1)`
把右起第一个0变成1	11 → 15	1011 → 1111	`x \| (x + 1)`
把右边连续的0变成1	20 → 23	10100 → 10111	`x \| (x - 1)`
取右边连续的1	23 → 7	10111 → 111	`(x ^ (x + 1)) >> 1`
去掉右起第一个1的左边	10 → 2	1010 → 10	`x & (x ^ (x - 1))`

7.1 判断一个数的奇偶性

#include <iostream>
using namespace std;

int main() {
    int num;
    cout << "请输入一个整数: ";
    cin >> num;

    if (num & 1) {
        cout << num << "是奇数" << endl;
    } else {
        cout << num << "是偶数" << endl;
    }

    return 0;
}

7.2 交换两个数

#include <iostream>
using namespace std;

int main() {
    int a = 5, b = 10;
    cout << "交换前: a = " << a << ", b = " << b << endl;

    // 使用异或运算交换两个数
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;

    cout << "交换后: a = " << a << ", b = " << b << endl;

    return 0;
}

7.3 查看特定位的值

#include <iostream>
using namespace std;

void printBinary(int num) {
    cout << "二进制表示: ";

    // 打印32位整数的每一位
    for(int i = 31; i >= 0; i--) {
        if((num >> i) & 1) {
            cout << "1";
        } else {
            cout << "0";
        }

        // 每8位添加一个空格，提高可读性
        if(i % 8 == 0) cout << " ";
    }
    cout << endl;
}

int main() {
    int num = 78;  // 二进制: 1001110
    printBinary(num);

    // 检查第4位(从0开始计数)是否为1
    int position = 4;
    if((num >> position) & 1) {
        cout << "第" << position << "位是1" << endl;
    } else {
        cout << "第" << position << "位是0" << endl;
    }

    return 0;
}

8. 总结

二进制和位运算是计算机科学的基础，理解这些概念对于编程和算法设计至关重要：

二进制是计算机的基础语言，只使用0和1两个数字表示所有信息
原码、反码和补码是表示有符号数的三种方式，其中补码在计算机中应用最广泛
位运算直接操作二进制位，包括与(&)、或(|)、异或(^)、取反(~)等操作
移位运算是非常高效的操作，左移相当于乘以2，右移相当于除以2
负数在计算机中采用补码表示，通过取反加一的方式得到
二进制加法是所有算术运算的基础，计算机通过加法实现其他算术运算

通过位运算，我们可以实现许多高效的算法和操作，比如判断奇偶性、交换两个数、检查特定位的值等。随着学习的深入，你会发现位运算在更多复杂算法中的应用。

练习题

将十进制数42转换为二进制
计算二进制数1101和1011的和
使用位运算判断一个数是否是2的幂
不使用第三个变量，交换两个整数的值
将十进制数-25转换为8位二进制补码表示
已知某数的补码是11110000，求这个数的原码和十进制值