本文轉自徐飛翔的“”

版權聲明：本文為博主原創文章，遵循版權協議，轉載請附上原文出處鏈接和本聲明。

在刷題過程中，我們經常會遇到需要判斷某個整數是奇數還是偶數的情況，這個時候，我們可能會采取取模的操作，直接判斷，如：

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]. //stackoverflow.com/questions/3909648/identify-odd-even-numbers-binary-vs-mod

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

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