学了位运算，但不会用怎么办？

当了士疑解惑辅导师后发现好多人不会用位运算，于是写了这篇文给初学者好好捋捋（Photo by Alexander Sinn on Unsplash ）

莱布尼茨：二进制乃是具有世界普遍性的、最完美的逻辑语言

大多数同学都会发现，BUAA 程设课上会学一节课的位运算，但也仅仅是学了，该用的时候还是不会用…

其实是老师讲的太糙了。位运算作为 C 语言的精髓之一，想要理解它就得从内存开始。

一、数据在内存中的存储

所有的程序，不管是大佬们写的，还是我们自己写的，都是在内存中以 0 和 1 的形式存在的。

比特、字节

内存中的所有0 1 都有特定的组织方式，也有对应的命名规范。

内存中，每一个存储 0 或 1 的位置，叫做一个比特（bit）
每 8 个相邻的比特，叫做一个字节（Byte）

Bit and Byte

根据高中简单的排列组合性质，我们可以很容易的知道

一个 bit 可以表示的数据量为 $2^1=2$
一个 Byte 可以表示的数据量为 $2^8 = 256$

整数的存储与表示

我们知道，不同类型的整数在内存中所占用的字节数不同，也就是所表示的数据范围不同，但它们都按照一定的对应法则实现了一个从 Bytes 到不同数字的双射 ，这个对应法则也就是补码。

把补码看成整数的编码方式对于初学者还是不太好接受的，但是把补码看成一种映射，再简单点，其实就是一种函数，这就好理解多了。

补码是 内存中的字节信息 到 其所表达数字 的函数

我们假设这种函数为

$number = f(bytes)$

再简化一点，其实就是

$N = f(B)$

这样的话，其实我们平时和程序之间的互动，就是解自变量和求函数值的过程

我们写char a = 5，编译执行，已知 N = 5，通过对应关系$B=f^{-1}(N) $，求解出内存中的字节信息 B: 00000101
我们写printf("%d", a) ，其实就是已知变量 a 的字节信息 B: 00000101，通过$N=f(B)$ 输出结果5

作此假设，有符号整数和无符号整数的区别也更好解释了

对于有符号整数signed char ，它遵循的映射关系就是我们学到的补码的样子，将00000101映射为5、将11111111映射为-1 ，此时一个字节的 256 种信息被映射到 $-128 $ ~ $ 127$ ，我们设这个映射关系为 $f_s$
对于无符号整数unsigned char，它遵循的映射关系就是正常二进制数的样子，将00000101映射为5、将11111111映射为255 ，此时一个字节的 256 种信息被映射到 $0$ ~ $255$ ，我们设这个映射关系为 $f_u$

这样一来，整数和内存信息之间的关系不就满足这样一个分段函数吗：

$N = f(B) =\begin{cases}f_s(B) &,\text{有符号整数} \\ f_u(B)&,\text{无符号整数}\end{cases}$

因此，无符号整数和有符号整数之间的关系也就变得一目了然了：无符号整数和有符号整数本质上就是映射关系的不同。这就是为什么 “将一个有符号负整数，强制转换为无符号整数，输出的结果就不一样了” 的原因，这个数在内存里其实一点都没变，变的只是它的映射关系 ，详见以下代码:

signed char a = -1;
printf("%d\n", (unsigned char)a);
/*
输出结果为:
255

*/

这个过程其实是这样的：

$-1(N) \stackrel{f_s^{-1}}{\longrightarrow} 11111111(B) \stackrel{f_u}{\longrightarrow} 255(N)$

二、除 2 取余——打印补码的“法宝”

~（明确说一下，这个“法宝”在这是贬义的。）~

为什么会有上面的“一”呢？其实主要是因为我想把大家思考问题的层次由数字表面拉向内存层面，但其实还有一个原因…… 当时一个大一小朋友问我：“补码到底咋算呀？”，我说：“补码不用算，直接用位运算取出来就行”，TA 说：“负数总要算的吧” ，结果一下子给我整不会了QAQ。问了问才知道，TA 打印补码就是用“除 2 取余”的方法，遇到负数就分类讨论…

所以另一个原因是，我想传达一下 虽然“除2取余”不是打印补码的最优解，但也不至于为负数分类讨论的事实

那么，用除 2 取余的方法，怎么打印整数的补码呢？

// 其实这样输出的结果是 “倒着的补码”，可以先用数组存着，最后倒序输出即可
// 因为只讲思路，所以逆序的部分就省略了
int num_to_print = ...;
unsigned int temp = (unsigned int)num_to_print;
while(temp){
    printf("%d", temp % 2);
    temp /= 2;
}

其实真就是很简单一件事，利用了“一”最后提到的 “有符号整数强制转换为无符号整数时，内存信息并没有变化” 。所以， 打印(unsigned int)num_to_print 的补码和打印num_to_print 的补码其实是一样的嘞 。既然无符号整数不用考虑负数情况，那就 “除 2 取余”打印无符号整数的补码 就好了呀！

三、用位运算打印补码

回到正经话题了，位运算到底怎么用？

要我说，要想能用好位运算，首先就是要非常熟练$B=f^{-1}(N)$ 的过程。在用位运算的时候，脑海里要有清晰的字节信息图，能够将B 与 N 对应起来，就像这样：

对应图

在这个部分，我们来详细讲一下，C语言如何通过位运算打印补码

0. 先复习一下 C 语言的位运算

按位与 &，对应比特位都为 1 则值为 1，否则值为 0 (0b1100 & 0b0101) == 0b0100
按位或|，对应比特位存在 1 则值为 1，否则值为 0 (0b1100 | 0b0101) == 0b1101
按位异或^ ，对应比特位不同则值为 1，否则值为 0 (0b1100 ^ 0b0101) == 0b1001
按位取反~，将所有比特位的值翻转 ~(0b1100) == 0b0011
左移<< x ，将所有比特位向左移 x 位，右端补零 (0b1100 << 1) == (0b1000)
右移>> x ，将所有比特位向右移 x 位，左端根据最高比特位和整数有无符号选择补 0 还是补 1
- 例如signed char 类型的 0b00110011 ，(0b00110011 >> 1) == 0b00011001
- 例如 signed char 类型的 0b10110011 ，(0b10110011 >> 1) == 0b11011001
- 例如unsigned char 类型的 0b10110011 ，(0b10110011 >> 1) == 0b01011001

大概就是这么多了，其实道理是很简单的。不过位运算有一个比较容易忽略的问题，那就是优先级

部分位运算符号的优先级是要比> 、<、== 这种判断运算符要低的，所以使用的时候还是要多加括号

1. 判断某个位的值

整数以补码的形式存储在内存中，那么打印某个数的补码，实际上就是要判断它在内存中的情况，打印它在内存中各个比特位的值

那么我们可以很自然地想到，这需要两个步骤：

找到一种方法，可以遍历一个整数的所有比特位
将某个比特位的0 、1 两种可能情况判断出来

对于遍历比特位，我们在 “0.” 中找一找，发现只有左移 << 和右移>> 两个位运算操作可以帮助我们实现

对于判断某个位的值，我们应该怎么办呢？

我们先拿简单的5 也就是0b0101 来考虑，如何判断它的第 0 位是 1 呢：

先想想单目运算符 ~ ，这肯定是不行的。因为单目运算符只有一个量参与运算，也就是说一个确定数5 和~ 参与运算，只能得出一种结果，无法判断0 、1 两种情况。也就是说，我们至少要用一个双目位运算符

剩下的& 、| 、^ 中，先考虑^ 。我们要判断第 0 位的值，也就是0b010x 中x 的值，那就用一个最简单的0b0001 也就是1 吧。

我们试一下，如果 x=1，(0b0001 ^ 0b0101) == 0b0100 ；如果x=0 ，也就是0b0100 ，那么再运算一下(0b0001 ^ 0b0100) == 0b0101 。哇确实不一样了诶!!! 也就是说，其实^ 是可以分辨的。我们用0b0001 和 0b010x 做按位异或运算，如果结果是0b0100 那么x 就是1 ；如果结果是0b0101 那么x 就是0
我们改变待判断数的第 1 ~ 3 位。例如，我们判断0b110x 的第 0 位，那么分别用0b1101 、0b1100 和0b0001 做按位异或运算，结果是0b1100 和 0b1101 。也就是说，我们用0b0001 和 0b110x 做按位异或运算，如果结果是0b1100 那么x 就是1 ；如果结果是0b1101 那么x 就是0

可惜了，我们发现，如果第 1 ~ 3 位的值不同，判断标准也不同，这样就没法得到一个普适的规律

我们再考虑一下& 运算。我们可以惊讶地i发现 0b010x 与 0b0001 进行按位与运算，如果x=1 那么结果就是0b0001 ；如果 x=0 那么结果就是0b0000。而且无论其它比特位怎么变，结果依旧如此。那么我们就找到了一种普适的可以判断某个特定比特位值的方法：

如果要判断某个数的某个比特位的值 x，只需要构造一个除了待判比特位为 1 ，其余比特位均为 0 的数 0b00...1...00，将该数与待判断的数进行按位与运算，如果结果为 0 ，则 x=0 ；若非零，则 x=1。

那么如何构造0b00...1...00呢？其实很简单，还记得的上面的遍历吗？这不就是1 << m 嘛

2. 代码

好好好，终于到了要写代码的时候了

// 这次输出的就是正着的补码
int num_to_print = ...;
for(int i = 31; i >= 0; i--){ //遍历
    if( ( num_to_print & (1 << i) ) == 0 ){ //判读
        printf("1"); //输出
    }else{
        printf("0"); //输出
    }
}

~喔喔喔，完结撒花？？？~

3. 拓展*

咳咳，不是还有按位或|吗？

嘿嘿，其实没必要讨论它，因为学过 BUAA 某国家精品课后，你就会发现，其实 $a~ \text{＆}~ b \equiv \text{～}( \text{～}a~ |~\text{～}b)$

什么意思呢？就是说按位与这种运算可以由按位或和取反两种运算表示。按位与能实现的，你通过按位或和取反一样能实现。

再说严格点，我们上文中说^ 没法得到一个普适的判断标准，但是^ 配合上~ 其实就能了。因为 {$~|, \text{～}$} 、{$\land, \text{～}$} 都是完备集。

所以说，大家可以动动脑筋，想想如何用 | 实现位运算打印补码的功能呢？

4. 拓展$^2$*

用位运算和遍历的方式已经能够很快地实现打印补码的操作了，但是没有最快只有更快！再深入一下就不是面对初学者的文章了。所以呢，在此就不细说了（~才不是因为我看不懂呢~），有兴趣的话移步以下链接：

https://zhuanlan.zhihu.com/p/390624822?utm_psn=1740495382910631936https://zhuanlan.zhihu.com/p/390624822?utm_psn=1740495382910631936

四、位运算还有哪些妙用？

其实位运算的奇淫用法数不胜数，在此给大家一些常用的

1. 判断奇偶数

道理其实很简单，大家想想就能明白

int a = ...;
if( a & 1 == 0 ){
    //奇数
}else{
    //偶数
}

2. 乘除模 2 的整数幂

这个大家应该也知道

(2 * x) == (x << 1)
(4 * x) == (x << 2)
    
(x / 4) == (x >> 2)
// 能想通奇偶数那个其实这个也差不多了
(x % 4) == (x & 0b11)

3. 判断 x 是否为 2 的整数幂

就是判断 x 是不是 1，2，4，8，16 …

//不考虑负数哦，要考虑的话自己加判断
if( (x & (x-1U)) == 0U ){
    // 是
}

4. 计算汉明距离

致敬 22 级信类数据结构大作业

汉明距离就是两个整数 n1 、n2 ，它们的 2 进制中 1 的个数的差

原理大家可以自己查，这要是详细解释的话又是一篇文章

int getHammingDis(int n1, int n2){
    int temp = n1 ^ n2;
    int hammingDis = 0;
    while (temp) {
        temp = (temp - 1) & temp;
        hammingDis++;
    }
}

5. swap

开始抽象了…

...
a ^= b; // a = a^b
b ^= a; // b = b^(a^b) = (b^b)^a = a
a ^= b; // a = (a^b)^a = (a^a)^b = b
...

6. 神奇的 0x5f3759df

做题别用，仅作了解，因为它多快好省~

这是一个辉煌的壮举

详情请移步:

https://b23.tv/WcbUZMhhttps://b23.tv/WcbUZMh

float Q_rsqrt( float number )
{
	long i;
	float x2, y;
	const float threehalfs = 1.5F;
 
	x2 = number * 0.5F;
	y  = number;
	i  = * ( long * ) &y;                       // evil floating point bit level hacking
	i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
	y  = * ( float * ) &i;
	y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//      y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed
 
	return y;
}

五、结尾

1. 位运算到底有什么用？

位运算是非常底层的运算，它的执行速度特别快，远超一般的加减乘除，在程序中使用位运算可以加快程序的执行速度（尤其是在卷 DS 大作业的时候）。
位运算为进行位级别的操作提供了可行的方法，在更加底层的设备上（如单片机）方便开发者直接操作寄存器。
位运算可以帮助进一步节约资源，打破以字节为单位的存储方式，进一步节省存储空间。

2. 使用位运算的建议

使用位运算确实可以让程序更快，但同时也会让程序更难懂，降低了代码的可维护性。同时，目前的许多编译器都能够针对平时经常使用的一些操作进行优化（比如用位运算优化乘除 2 ），因此也没必要刻意使用位运算。所以说，在项目中使用位运算与否也是一个值得考虑的问题。

真的完结撒花了…

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。