位运算

第 29 课，共 30 课 · 第 6 部分 · 再往前 · 约 15 分钟

在电脑里，每个整数都是一排位（bit），也就是一排 0 和 1。位运算直接对这些位动手。为了看清楚，我们自己写一个小函数，显示一个数的最后 8 位（printf 没有显示二进制的格式符）：

main.c

1#include <stdio.h>2 3void print_bits(unsigned int x) {4    for (int i = 7; i >= 0; i--) {5        int bit = (x >> i) & 1;6        printf("%d", bit);7    }8    printf("\n");9}10 11int main(void) {12    int numbers[5] = {1, 2, 5, 13, 255};13    for (int i = 0; i < 5; i++) {14        printf("%3d = ", numbers[i]);15        print_bits(numbers[i]);16    }17    return 0;18}

输出

  1 = 00000001
  2 = 00000010
  5 = 00000101
 13 = 00001101
255 = 11111111

unsigned int 是不能为负的 int，做位运算时常用它。print_bits 是怎么做到的，学完这一课就明白了；现在先看它显示了什么。

二进制

平时用的数，每一位是右边那一位的 10 倍：个位、十位、百位。二进制里，每一位是右边那一位的 2 倍。下面是 13 的 8 位二进制：

这一位值	128	64	32	16	8	4	2	1
位	0	0	0	0	1	1	0	1

是 1 的那几位值 8、4、1，8 + 4 + 1 = 13。8 位能表示的最大的数是全 1：128 + 64 + ... + 1 = 255。一个 int 有 32 位，这里只显示最后 8 位，小的数够用了。

数位的时候从右往左数，从 0 开始：第 0 位值 1，第 1 位值 2，第 2 位值 4，依此类推。

& 和 |

&（与）和 |（或）把两个数一位一位地对着比：

a	b	a & b	a \| b	a ^ b
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

& 要两个都是 1 才得 1；| 只要有一个是 1 就得 1。（^ 下一节讲。）

main.c

1#include <stdio.h>2 3void print_bits(unsigned int x) {4    for (int i = 7; i >= 0; i--) {5        int bit = (x >> i) & 1;6        printf("%d", bit);7    }8    printf("\n");9}10 11int main(void) {12    int a = 12;13    int b = 10;14    printf("a     = ");15    print_bits(a);16    printf("b     = ");17    print_bits(b);18    printf("a & b = ");19    print_bits(a & b);20    printf("a | b = ");21    print_bits(a | b);22    printf("%d %d\n", a & b, a | b);23    return 0;24}

输出

a     = 00001100
b     = 00001010
a & b = 00001000
a | b = 00001110
8 14

别和 &&、||（第 5 课）搞混。那两个看的是整个值的真假，结果是 1 或 0。12 && 10 是 1，12 & 10 却是 8。

^ 和 ~

^（异或）在两位不一样时得 1。同一个 ^ b 做两次，就变回原来的数。~ 只要一个数，把每一位都翻过来：0 变 1，1 变 0。

main.c

1#include <stdio.h>2 3void print_bits(unsigned int x) {4    for (int i = 7; i >= 0; i--) {5        int bit = (x >> i) & 1;6        printf("%d", bit);7    }8    printf("\n");9}10 11int main(void) {12    int a = 12;13    int b = 10;14    printf("a ^ b       = ");15    print_bits(a ^ b);16    printf("(a ^ b) ^ b = ");17    print_bits((a ^ b) ^ b);18    printf("~a          = ");19    print_bits(~a);20    return 0;21}

输出

a ^ b       = 00000110
(a ^ b) ^ b = 00001100
~a          = 11110011

~a 翻的是全部 32 位，不只是这里显示的 8 位，所以当成 int 看，它是个负数。它单独用的时候不多，在后面「开关」一节里就能看到它的用处。

移位：<< 和 >>

x << n 把每一位往左挪 n 格，右边补 0。往左一格，值就翻一倍，所以左移 1 位就是乘以 2。x >> n 往右挪，挪出去的位就丢了，所以右移 1 位是除以 2，余数不要。

main.c

1#include <stdio.h>2 3int main(void) {4    for (int i = 0; i < 8; i++) {5        printf("%d ", 1 << i);6    }7    printf("\n");8    printf("%d %d %d\n", 5 << 1, 5 << 2, 5 << 3);9    printf("%d %d %d\n", 40 >> 1, 40 >> 2, 41 >> 1);10    return 0;11}

输出

1 2 4 8 16 32 64 128 
10 20 40
20 10 20

1 << i 是只有第 i 位是 1 的数：1、2、4、8……后面会常用到。现在 print_bits 也看得懂了：x >> i 把第 i 位挪到最右边，& 1 只留下最后这一位。

先猜一猜

这段程序显示什么？

1#include <stdio.h>2 3int main(void) {4    printf("%d\n", 3 << 4);5    return 0;6}

左移 4 位就是乘 4 次 2：3 × 16 = 48。从位上看，00000011 变成了 00110000。

输出

移的位数要比总位数少（int 就是少于 32），也不要把负数往左移：这两种都是未定义行为。

判断奇偶

第 0 位值 1，其他每一位的值都是偶数。所以一个数是奇数，正好就是它的第 0 位是 1。n & 1 就能告诉你：

main.c

1#include <stdio.h>2 3int main(void) {4    int numbers[5] = {7, 10, 23, 64, 0};5    for (int i = 0; i < 5; i++) {6        if (numbers[i] & 1) {7            printf("%d 是奇数\n", numbers[i]);8        } else {9            printf("%d 是偶数\n", numbers[i]);10        }11    }12    return 0;13}

输出

7 是奇数
10 是偶数
23 是奇数
64 是偶数
0 是偶数

对不是负数的数，n % 2 == 1 也能做同样的事。哪个读起来清楚就用哪个，编译器常常把两种写法变成一样的东西。

一个 int 存一组开关

一个文件可以读、可以写、可以运行，每一样都是「是」或「否」。不用三个变量，给每一样分一位，全放在一个 int 里就行。每个名字是只有一位是 1 的数（用第 28 课的 #define）：

想做什么	写法
打开	`perms \|= WRITE;`
关掉	`perms &= ~WRITE;`
翻过来	`perms ^= WRITE;`
看看开没开	`if (perms & WRITE)`

main.c

1#include <stdio.h>2 3#define READ (1 << 0)4#define WRITE (1 << 1)5#define RUN (1 << 2)6 7void show(int perms) {8    char text[] = "---";9    if (perms & READ) {10        text[0] = 'r';11    }12    if (perms & WRITE) {13        text[1] = 'w';14    }15    if (perms & RUN) {16        text[2] = 'x';17    }18    printf("%s  (%d)\n", text, perms);19}20 21int main(void) {22    int perms = READ | WRITE;23    show(perms);24    perms |= RUN;25    show(perms);26    perms &= ~WRITE;27    show(perms);28    perms ^= READ;29    show(perms);30    return 0;31}

输出

rw-  (3)
rwx  (7)
r-x  (5)
--x  (4)

~WRITE 除了 WRITE 那一位，别的位全是 1，所以 & ~WRITE 只关掉这一位，其余的不动。点单步，看 perms 从 3 变成 7，再变成 5，最后是 4。

练一练

写好代码，点检查。提示随便看，实在想不出来再看答案。

练习 1

数一数有几个 1

数一数 n 的二进制里有几位是 1。45 的二进制是 101101，所以显示 45 有 4 个 1。

要显示

45 有 4 个 1

exercise1.c

1#include <stdio.h>2 3int main(void) {4    int n = 45;5 6    return 0;7}

输出

点「运行」或按 Ctrl+Enter

练习 2

用移位代替乘除

price 的单位是分。用 << 和 >>（不用 * 和 /）显示它的 2 倍、8 倍和一半：2 倍：300、8 倍：1200、一半：75。

要显示

2 倍：300
8 倍：1200
一半：75

exercise2.c

1#include <stdio.h>2 3int main(void) {4    int price = 150;5 6    return 0;7}

输出

点「运行」或按 Ctrl+Enter

练习 3

改设置

settings 一开始打开了声音和深色模式。用位运算打开 ALERTS、关掉 SOUND，让程序显示 声音：关、深色：开、提醒：开。

要显示

声音：关
深色：开
提醒：开

exercise3.c

1#include <stdio.h>2 3#define SOUND (1 << 0)4#define DARK (1 << 1)5#define ALERTS (1 << 2)6 7int main(void) {8    int settings = SOUND | DARK;9 10    if (settings & SOUND) {11        printf("声音：开\n");12    } else {13        printf("声音：关\n");14    }15    if (settings & DARK) {16        printf("深色：开\n");17    } else {18        printf("深色：关\n");19    }20    if (settings & ALERTS) {21        printf("提醒：开\n");22    } else {23        printf("提醒：关\n");24    }25    return 0;26}

输出

点「运行」或按 Ctrl+Enter

这一课学会了

整数是一排位；二进制里每一位是右边那一位的 2 倍（1、2、4、8……）。
& 留下两边都是 1 的位，| 留下有一边是 1 的位，^ 留下正好一边是 1 的位；~ 把每一位翻过来。它们不是 && 和 ||。
x << n 是乘 n 次 2；x >> n 是除 n 次 2，余数不要。1 << i 只有第 i 位是 1。
n & 1 对奇数是 1，对偶数是 0。
一个 int 存一组开关：|= 打开，&= ~ 关掉，^= 翻过来，& 看开没开。