位运算 | Alan Wang

type

status

date

slug

summary

什么是位运算

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and 运算本来是一个逻辑运算符，但整数与整数之间也可以进行 and 运算。举个例子，6 的二进制是 110，11 的二进制是 1011，那么6 and 11 的结果就是 2，它是二进制对应位进行逻辑运算的结果（0 表示 False， 1 表示 True，空位都当 0 处理）：

由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。

符号	描述	运算规则
&	与	两个位都为 1 时，结果才为 1
\|	或	两个位都为 0 时，结果才为 0
^	异或	两个位相同为 0，相异为 1
~	取反	0 变 1，1 变 0
<<	左移	各二进位全部左移若干位，高位丟弃，低位补 O
>>	右移	各二进位全部右移若干位，对无符号数，高位补 0，有符号数，各编译器处理方法不样，有的补符号位（算术右移），有的补0（逻辑右移）

XOR - 异或

异或：相同为 0，不同为 1。也可用「不进位加法」来理解。

异或操作的一些特点：

实战常用的位运算操作

更为复杂的位运算操作

将x最右边的n位清零：x & ( ~0 << n )

获取x的第n位值（0 或者 1）：( x >> n ) & 1

获取x的第n 位的幂值：x & ( 1 << ( n - 1 ))

仅将第n位置为1：x | ( 1 << n)

仅将第n位置为0：x & ( ~( 1 << n ))

将x最高位至第n位（含）清零：x & (( 1 << n) - 1 )

将第n位至第0位（含）清零：x & ( ~(( 1 << ( n + 1)) -

内建函数

GCC 中还有一些用于位运算的内建函数：

int __builtin_ffs(int x) ：返回 x 的二进制末尾最后一个 1 的位置，位置的编号从 1 开始（最低位编号为 1 ）。当 x 为 0 时返回 0。

int __builtin_clz(unsigned int x) ：返回 x 的二进制的前导 0 的个数。当 x 为 0 时，结果未定义。

int __builtin_ctz(unsigned int x) ：返回 x 的二进制末尾连续 0 的个数。当 x 为 0 时，结果未定义。

int __builtin_clrsb(int x) ：当 x 的符号位为 0 时返回 x 的二进制的前导 0 的个数减一，否则返回 x 的二进制的前导 1 的个数减一。

int __builtin_popcount(unsigned int x) ：返回 x 的二进制中 1 的个数。

int __builtin_parity(unsigned int x) ：判断 x 的二进制中 1 的个数的奇偶性。

这些函数都可以在函数名末尾添加 l 或 ll （如 __builtin_popcountll ）来使参数类型变为 ( unsigned ) long 或 ( unsigned ) long long （返回值仍然是 int 类型）。

例如，我们有时候希望求出一个数以二为底的对数，如果不考虑 0 的特殊情况，就相当于这个数二进制的位数减去一 ，而一个数 n 的二进制表示的位数可以使用 32 - __builtin_clz(n) 表示，因此 31 - __builtin_clz(n) 就可以求出 n 以二为底的对数。

由于这些函数是内建函数，经过了编译器的高度优化，运行速度十分快（有些甚至只需要一条指令）。

📎 参考

位运算