本文转自徐飞翔的“用“位操作”取代“取模操作”判断奇数偶数”

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

在刷题过程中，我们经常会遇到需要判断某个整数是奇数还是偶数的情况，这个时候，我们可能会采取取模的操作，直接判断，如：

num % 2 == 0;
num % 2 == 1;

然而，取模操作是非常慢的（按照速度来说，位移操作>=加减法>>乘除法，取模，具体见文末的备注），因此我们应该尽量避免使用取模操作，在判断奇数偶数时，我们可以用位操作替代取模操作，因为我们知道，偶数可以被2整除，那么其最低有效位必然是0，而奇数的相反，则是1，因此可以简单用以下语句取代：

num & 0x01 == 0; 
num & 0x01 == 1;

实际上，在GCC中，其对“模2”操作的优化中，就是用“位与”进行取代的[1]，如：

cpp_code            uint ix = 3;
0000003c  mov         dword ptr [ebp-40h],3 
cpp_code            bool even = ix % 2 == 0;
00000043  mov         eax,dword ptr [ebp-40h] 
00000046  and         eax,1 
00000049  test        eax,eax 
0000004b  sete        al   
0000004e  movzx       eax,al 
00000051  mov         dword ptr [ebp-44h],eax 

有些平台，比如LeetCode中，并没有这种优化，因此需要自己进行显式地优化。

然而，我们还需要注意到，通常我们的位操作都是对无符号数进行的，如果对有符号数进行操作，可能会出现0表示的不一致问题，例如：

int num = 4;
cout << (num & 0x01) << endl;

这个应该输出0，实际上其输出也是0，那么我们看下一句：

cout << (num & 0x01 == 0) << endl;

这个我们期望它输出的是1，表示的确是偶数，但是其实实际上运行是输出的0，因为这两个0的表示不统一，我们需要显式将前者转成无符号数，如：

cout << ((unsigned int)(num & 0x01) == 0) << endl;

这样就是输出期望中的1了，这点需要特别注意下，容易坑到人。

备注： 以AMD k7处理器为例子，常见的算术，逻辑指令的延迟（latency）表[2]，这里的延迟指的是输入数据到输出数据之间的时间，注意到这里提到的延迟是最小值，没有考虑到实际中的内存取值，高速缓存missing之类的情况的。

取模操作通常是结合除法指令DIV实现的，因此延迟通常可以参考除法的，我们发现，除法的延迟特别的大，而乘法其次，加减法，逻辑运算通常只需要一个机器周期即可。

Reference

[1]. https://stackoverflow.com/questions/3909648/identify-odd-even-numbers-binary-vs-mod

[2]. https://www.agner.org/optimize/instruction_tables.pdf

[3]. https://bbs.csdn.net/topics/340234342