上QQ阅读APP看书，第一时间看更新
4.3 位运算
二进制数据的运算称为位运算，位运算操作符如下。
- “<<”：左移运算，最高位左移到CF中，最低位零。
- “>>”：右移运算，最高位不变，最低位右移到CF中。
- “|”：位或运算，在两个数的相同位上，只要有一个为1，则结果为1。
- “&”：位与运算，在两个数的相同位上，只有同时为1时，结果才为1。
- “^”：异或运算，在两个数的相同位上，当两个值相同时为0，不同时为1。
- “~”：取反运算，将操作数每一位上的1变0，0变1。
在程序算法中大量使用位运算，如不可逆算法MD5，就是通过大量位运算完成的。如何使一个数不可逆转呢？利用位运算就可以达到这个目的，如x & 0结果为0，而根据结果，是不可以逆推x的值的。由于大多数位运算会导致数据信息的丢失（取反~和异或^可以反推），因此，在知道原算法的前提下，使用逆转算法是无法计算出原数据的。在算术运算中，编译器会将各种运算转换成位运算，因此掌握位运算对于学会算法识别是一件非常重要的事。在编译器中，位运算符号又是如何转换成汇编代码的呢？请看代码清单4-22。
代码清单4-22 位运算Debug版
// C++源码
#include <stdio.h>
int main(int argc, char* argv[]) {
argc = argc << 3; //将变量argc左移3位
argc = argc >> 5; //将变量argc右移5位
argc = argc | 0xFFFF0000; //将变量argc与0xFFFF0000做位或运算
argc = argc & 0x0000FFFF; //将变量argc与0x0000FFFF做位与运算
argc = argc ^ 0xFFFF0000; //将变量argc与0x FFFF0000做异或运算
argc = ~argc; //对变量argc按位取反
return argc; //返回argc
}
//x86_vs对应汇编代码讲解
00401000 push ebp
00401001 mov ebp, esp
00401003 mov eax, [ebp+8] ;eax=argc
00401006 shl eax, 3 ;eax=argc<<3
00401009 mov [ebp+8], eax ;argc=argc<<3
0040100C mov ecx, [ebp+8] ;ecx=argc
0040100F sar ecx, 5 ;有符号右移，ecx=argc>>5
00401012 mov [ebp+8], ecx ;argc=argc>>5
00401015 mov edx, [ebp+8] ;edx=argc
00401018 or edx, 0FFFF0000h ;edx=argc|0xFFFF0000
0040101E mov [ebp+8], edx ;argc=argc|0xFFFF0000
00401021 mov eax, [ebp+8] ;eax=argc
00401024 and eax, 0FFFFh ;eax=argc & 0x0000FFFF
00401029 mov [ebp+8], eax ;argc=argc & 0x0000FFFF
0040102C mov ecx, [ebp+8] ;ecx=argc
0040102F xor ecx, 0FFFF0000h ;ecx=argc ^ 0xFFFF0000
00401035 mov [ebp+8], ecx ;argc=argc ^ 0xFFFF0000
00401038 mov edx, [ebp+8] ;edx=argc
0040103B not edx ;edx=~argc
0040103D mov [ebp+8], edx ;argc=~argc
00401040 mov eax, [ebp+8]
00401043 pop ebp
00401044 retn ;return argc
//x86_gcc 对应汇编代码相似，省略
//x86_clang对应汇编代码相似，省略
//x64_vs 对应汇编代码相似，省略
//x64_gcc 对应汇编代码相似，省略
//x64_clang对应汇编代码相似，省略
代码清单4-22演示了有符号数的移位运算，对于无符号数而言，转换的位移指令将会发生转变，如代码清单4-23所示。
代码清单4-23 无符号数位移（Debug版）
// C++源码
#include <stdio.h>
int main(int argc, char* argv[]) {
unsigned int n = argc;
n <<= 3;
n >>= 5;
return n;
}
//x86_vs对应汇编代码讲解
00401000 push ebp
00401001 mov ebp, esp
00401003 push ecx
00401004 mov eax, [ebp+8] ;eax=argc
00401007 mov [ebp-4], eax ;n=argc
0040100A mov ecx, [ebp-4] ;ecx=n
0040100D shl ecx, 3 ;ecx=argc<<3
00401010 mov [ebp-4], ecx ;n=argc << 3
00401013 mov edx, [ebp-4] ;edx=n
00401016 shr edx, 5 ;无符号右移，edx=argc >> 5
00401019 mov [ebp-4], edx ;n=argc >> 5
0040101C mov eax, [ebp-4]
0040101F mov esp, ebp
00401021 pop ebp
00401022 retn
//x86_gcc 对应汇编代码相似，省略
//x86_clang对应汇编代码相似，省略
//x64_vs 对应汇编代码相似，省略
//x64_gcc 对应汇编代码相似，省略
//x64_clang对应汇编代码相似，省略
在代码清单4-23中，对于左移运算而言，无符号数和有符号数的移位操作是一样的，都不需要考虑符号位。但右移运算则有变化，有符号数对应的指令为sar，可以保留符号位；无符号数不需要符号位，所以直接使用shr将最高位补0。