本文轉(zhuǎn)自徐飛翔的“用“位操作”取代“取模操作”判斷奇數(shù)偶數(shù)”

版權(quán)聲明：本文為博主原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接和本聲明。

在刷題過(guò)程中，我們經(jīng)常會(huì)遇到需要判斷某個(gè)整數(shù)是奇數(shù)還是偶數(shù)的情況，這個(gè)時(shí)候，我們可能會(huì)采取取模的操作，直接判斷，如：

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

然而，取模操作是非常慢的（按照速度來(lái)說(shuō)，位移操作>=加減法>>乘除法，取模，具體見(jiàn)文末的備注），因此我們應(yīng)該盡量避免使用取模操作，在判斷奇數(shù)偶數(shù)時(shí)，我們可以用位操作替代取模操作，因?yàn)槲覀冎?，偶?shù)可以被2整除，那么其最低有效位必然是0，而奇數(shù)的相反，則是1，因此可以簡(jiǎn)單用以下語(yǔ)句取代：

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

實(shí)際上，在GCC中，其對(duì)“模2”操作的優(yōu)化中，就是用“位與”進(jìn)行取代的[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 

有些平臺(tái)，比如LeetCode中，并沒(méi)有這種優(yōu)化，因此需要自己進(jìn)行顯式地優(yōu)化。

然而，我們還需要注意到，通常我們的位操作都是對(duì)無(wú)符號(hào)數(shù)進(jìn)行的，如果對(duì)有符號(hào)數(shù)進(jìn)行操作，可能會(huì)出現(xiàn)0表示的不一致問(wèn)題，例如：

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

這個(gè)應(yīng)該輸出0，實(shí)際上其輸出也是0，那么我們看下一句：

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

這個(gè)我們期望它輸出的是1，表示的確是偶數(shù)，但是其實(shí)實(shí)際上運(yùn)行是輸出的0，因?yàn)檫@兩個(gè)0的表示不統(tǒng)一，我們需要顯式將前者轉(zhuǎn)成無(wú)符號(hào)數(shù)，如：

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

這樣就是輸出期望中的1了，這點(diǎn)需要特別注意下，容易坑到人。

備注： 以AMD k7處理器為例子，常見(jiàn)的算術(shù)，邏輯指令的延遲（latency）表[2]，這里的延遲指的是輸入數(shù)據(jù)到輸出數(shù)據(jù)之間的時(shí)間，注意到這里提到的延遲是最小值，沒(méi)有考慮到實(shí)際中的內(nèi)存取值，高速緩存missing之類的情況的。

取模操作通常是結(jié)合除法指令DIV實(shí)現(xiàn)的，因此延遲通常可以參考除法的，我們發(fā)現(xiàn)，除法的延遲特別的大，而乘法其次，加減法，邏輯運(yùn)算通常只需要一個(gè)機(jī)器周期即可。

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