位运算和其他运算符 ¶

位运算 | Linux C编程一站式学习

其它运算符 | Linux C编程一站式学习

Arithmetic operators | cppreference

约定 ¶

位运算只针对无符号类型进行. 有符号数的右移和左移溢出都不适合拿来写可移植代码.
移位次数必须落在 [0, 宽度). 负数或大于等于宽度都是undefined behavior. 宽度按提升之后的左操作数算.
== 比 & | ^ 更紧, + - 比 << >> 更紧. 比较标志位, 以及"移位再加减", 都要加括号.
掩码写成 unsigned 常量, 例如 1U << n. 裸 1 << 31 在 32 位 int 上是有符号溢出, 属于 undefined behavior.
复合赋值, ++ / -- 对左操作数只求值一次. 左操作数有副作用时不要展开成两次求值的写法.

位运算 ¶

与, 或, 异或, 取反 ¶

同一位置上的两个 bit 各自做逻辑运算, 互不影响.

运算符	名字	这一位的结果
`&`	按位与	两位都是 1 才是 1
`\\|`	按位或	有一位是 1 就是 1
`^`	按位异或	两位不同才是 1
`~`	按位取反	0 变 1, 1 变 0

unsigned char c = 0xfc;
unsigned int i = ~c; /* 0xffffff03, not 0x03 */

0xfc 这个常量是 int, 赋给 c 时截成 unsigned char, 值仍是 0xfc. 算 ~c 时 c 先提升成 int 的 0x000000fc, 再取反, 得到 0xffffff03.

新手误区

在上面的例子中, 把 ~c 想成"8 位取反得到 0x03"就错了. 无符号类型上, ~E 等于该类型最大值减 E, 即 ~E == UMax - E.

移位 ¶

<< 把各位向高位移, 低位补 0, 移出宽度的位丢掉. >> 向低位移, 移出的低位丢掉.

两边都先做整数提升, 不做寻常算术转换. 结果类型等于提升后的左操作数. 所以 unsigned char 左移, 实际是在 int 上移.

无符号数, 以及非负的有符号数:

左移 1 位等于乘 \(2\), 左移 \(n\) 位等于乘 \(2^n\). 无符号溢出按模 \(2^N\) 截断, 这是定义好的.
右移 1 位等于除以 \(2\), 小数部分丢掉 (向 0 截断).

有符号数不要依赖移位:

左操作数是负数, 或者非负数左移后装不进结果类型 (含移进符号位), 都是 undefined behavior. 教材里"负数左移仍等于乘 2"只在没踩到这个前提时碰巧成立, 标准不保证.
负数右移是implementation-defined. x86 上的 gcc 会补符号位 (算术右移), 负数右移 1 位仍像除以 2. 换编译器可以改成补 0 (逻辑右移).

移位比乘法快, 是 CPU 的事实. 源码里该写乘法就写乘法, 编译器自己会把 i * 8 编译成移位.

int i = 0xcffffff3;
printf("%x\n", 0xcffffff3 >> 2); /* 33fffffc */
printf("%x\n", i >> 2);          /* gcc x86: f3fffffc */

0xcffffff3 装不进 32 位 int, 无后缀十六进制常量会提升成 unsigned int, 右移补 0. 赋给 int i 之后位型还在, 但类型变成有符号, 右移按实现补符号位. %x 只是按无符号把这些位打出来.

掩码 ¶

掩码标出要处理的那些位. 比如 0x0000ff00 表示 32 位整数里的 bit 8 到 bit 15.

unsigned int a = 0x12345678;
unsigned int mask = 0x0000ff00;

unsigned int mid = (a & mask) >> 8; /* 0x56, 取出 */
unsigned int cleared = a & ~mask;   /* 0x12340078, 清 0 */
unsigned int filled = a | mask;     /* 0x1234ff78, 置 1 */

常见的掩码操作:

目的	写法
取出	`(a & mask) >> shift`
清 0	`a & ~mask`
置 1	`a \\| mask`
翻转	`a ^ mask`

低 \(n\) 位全是 1 的掩码可以写成 ~(~0U << n). n 必须小于 unsigned int 的宽度, 等于宽度时 << 已是 undefined behavior.

Example

比如统计一个无符号整数二进制表示中 1 的个数可以用 x &= x - 1: 每次消掉最低的那个 1, 循环次数等于 x 中 1 的个数. 循环右移是把移出的低位补回高位:

unsigned int rotate_right(unsigned int x, unsigned int n)
{
    unsigned int w = sizeof x * CHAR_BIT;
    n %= w;
    if (n == 0)
        return x;
    return (x >> n) | (x << (w - n));
}

n 先对宽度取模. n == 0 时必须直接返回: 否则 x << w 的移位次数等于宽度, 是 undefined behavior.

异或的几个性质 ¶

x ^ x == 0, x ^ 0 == x. x86 上编译器常用 xorl %eax, %eax 把寄存器清 0: 只在 CPU 内部算, 这样无需从内存取立即数 0.
某一位与 0 异或保持原值, 与 1 异或变成相反值. 所以 a ^ (1U << n) 只翻转第 n 位.
一串 bit 异或的结果是 1, 当且仅当其中 1 的个数是奇数. 串口的奇偶校验位就是这一条: 数据和校验位一起发出去, 接收方再异或一遍, 对不上就说明这一帧大概坏了. 它查不出两位同时翻转.
x ^ x ^ y == y. 由此可以不借助临时变量交换两个数:
```
a = a ^ b;
b = b ^ a;
a = a ^ b;
```
记初值为 \(a_0\), \(b_0\). 第一步 a 变成 \(a_0 \oplus b_0\). 第二步 b 变成 \(b_0 \oplus (a_0 \oplus b_0) = a_0\). 第三步 a 变成 \((a_0 \oplus b_0) \oplus a_0 = b_0\).

异或交换的局限

a 和 b 必须是两个不同的对象. 自己和自己交换会先把值清成 0. 别名 (两个指针指向同一块内存) 同样会清掉. 用临时变量则没有这个问题, 编译器也一样能优化掉. 这条只用来理解异或, 不要写进业务代码.

RAID的校验盘用的就是性质 3 和 4: 校验块是各数据块的异或. 丢一块时, 用剩下的块再异或一次就能把丢掉的那块算回来.

其他运算符 ¶

复合赋值 ¶

*= /= %= += -= <<= >>= &= ^= |=

a += 1 等价于 a = a + 1, 但 a 只求值一次. 没有副作用时结果相同, 只是少算一遍下标或指针. 有副作用时结果可能不同:

a[i + j] += 1;           /* i + j 算一次 */
a[foo()] += 1;           /* foo() 调用一次 */
a[foo()] = a[foo()] + 1; /* foo() 调用两次 */

运算发生在提升后的类型上, 结果再按赋值规则转回左操作数的类型. ++i 等价于 i += 1, --i 等价于 i -= 1, 同样只求值一次.

条件运算符 ¶

?: 是 C 里唯一的三目运算符: 条件 ? 表达式2 : 表达式3. 条件必须是标量 (整数, 浮点, 指针). 条件非 0 则取表达式 2, 否则取表达式 3. 只有被选中的那个分支会求值.

两个分支都是算术类型时, 做寻常算术转换, 得到整个表达式的类型. 并不要求两边类型字面相同: 1 ? 1 : 1.0 的类型是 double. 都是 void, 或都是兼容类型的指针时, 也合法. 整个表达式不是左值, 不能写 (cond ? a : b) = 1.

int max(int a, int b)
{
    return (a > b) ? a : b;
}

若分支很长, 或两边类型容易被隐式转换带偏时, 写成 if...else... 更清楚.

逗号运算符 ¶

表达式1, 表达式2. 先算左边, 把值丢掉 (副作用留下), 再算右边, 整个表达式的值是右边的值. 两边类型不必相同. 左结合, 所以 a, b, c 从左到右求值, 值等于 c. 左右之间有序列点: 左边的副作用在右边开始前完成.

函数参数里的逗号是分隔符, 不是这个运算符. 要在参数里用它, 必须再加一层括号:

f(a, (t = 3, t + 2), c); /* 第二个实参的值是 t + 2 */

for 的循环头里常见它: for (i = 0, j = n; i < j; i++, j--).

sizeof 与 typedef ¶

sizeof 有两种写法:

sizeof 表达式 或 sizeof(表达式). 括号可有可无. 一般不求值, 只看类型占多少字节. 操作数是变长数组 (VLA) 时例外, 长度要到运行时才知道, 表达式会求值.
sizeof(类型名). 括号不能省.

结果类型是 size_t, 定义在 <stddef.h>, 是某个无符号整数. 打印用 %zu. 用 %d 是把无符号值按有符号 int 来解释.

int a[12];
printf("%zu\n", sizeof a / sizeof a[0]); /* 12 */

数组还在 (没有退化成指针) 时, 这个比值就是元素个数, 并且是编译期常量. sizeof a 在常见 ILP32 上是 48, sizeof a[0] 是 4.

typedef 不是运算符, 是给已有类型起新名字. 写法可以当成"变量声明前面加了 typedef": 拿掉它, 剩下的应是一条合法的变量声明.

typedef unsigned long size_t; /* 某一平台上的一种定义, 不是标准规定 */
typedef char array_t[10];
array_t a;                    /* 等价于 char a[10]; */

标准规定 size_t 能装下任意对象的字节数, 但没规定它是 unsigned long 还是 unsigned long long. 所以不要把 size_t 和你猜的底层类型混在一次赋值里: 在 ILP32 上如果 size_t 比 unsigned long 宽, 赋过去会截掉高位.

类型名习惯加 _t. 内核代码中几乎不对结构体和指针使用 typedef.