小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

求整數(shù)中比特為1的二進(jìn)制位數(shù)

 WUCANADA 2012-04-25

求整數(shù)中比特為1的二進(jìn)制位數(shù)

分類： C/C++ 2009-11-14 01:05 1129人閱讀 評(píng)論(2) 收藏 舉報(bào)

 

好幾次在CSDN上看到別人討論如何求出一個(gè)整數(shù)的二進(jìn)制表示中狀態(tài)為1的比特位數(shù)。今天寫了個(gè)程序把從網(wǎng)上看來的加上自己想出來的共有5種方法測試了一下，覺得好玩，就寫了這篇博客。

首先簡單介紹一下這五種方法。

第一種：最簡單的，通過移位操作逐位測試并計(jì)數(shù)，不妨稱為“逐位測試法”；

第二種：注意到對(duì)于“單比特二進(jìn)制”而言，其狀態(tài)與數(shù)值“相同”。即對(duì)于單個(gè)比特的“數(shù)”而言，為0即表示數(shù)值0，“全部為1”即表示數(shù)值1（注意多比特?cái)?shù)值顯然沒有這個(gè)特點(diǎn)，比如一個(gè)字節(jié)有8個(gè)比特，當(dāng)8個(gè)比特全為1時(shí)并不代表整數(shù)8，而代表255）。利用這一特點(diǎn)，從單個(gè)比特開始，以相鄰的一位、兩位、四位、八位和十六位為分組，一組一組地相加并逐步累計(jì)，最終得出結(jié)果；不妨稱為“分組統(tǒng)計(jì)法”；

第三種：注意到一個(gè)整數(shù)減1的會(huì)把最后一位1變成0，而其后的0全變成1，利用這一特點(diǎn)，把一個(gè)數(shù)不斷與它減1后的結(jié)果做“按位與”，直到它變成0，那么循環(huán)的次數(shù)便是其狀態(tài)為1的比特位數(shù)。不妨稱之為“循環(huán)減一相與法”；

第四種：考虛到多數(shù)處理器都提供“找到第一個(gè)為1的比特位”這種指令，在我的PC上直接調(diào)用X86處理器的BSF或BSR指令，每次直接找到第一個(gè)不為0的位并消掉，直到該數(shù)變成0，那么循環(huán)的次數(shù)即為狀態(tài)為1的比特位數(shù)。這種不妨稱為“匯編嵌入法”；

第五種，一個(gè)字節(jié)一共有256種狀態(tài)，將每一個(gè)取值所對(duì)應(yīng)的0比特位數(shù)的事先寫在程序中（注意這些數(shù)值是有規(guī)律的），也耗不了太多內(nèi)存，然后程序運(yùn)行的時(shí)候，把整數(shù)的四個(gè)字節(jié)拆開逐字節(jié)查表并相加，這種可稱為“查表法”。

 

以下是程序。程序中對(duì)應(yīng)以上五種方法的函數(shù)分別命名為f1到f5。另外還有三個(gè)函數(shù)，correctness_test通過幾個(gè)簡單而又特殊的取值測試各個(gè)函數(shù)的正確性，相當(dāng)于一個(gè)小單元測試；performance_test則分別將這5個(gè)函數(shù)作用于一億個(gè)隨機(jī)整數(shù)同進(jìn)行性能測試；prepare_test_data則是準(zhǔn)備1億個(gè)隨機(jī)整數(shù)的程序（這個(gè)函數(shù)實(shí)際并沒有為測試數(shù)據(jù)提供足夠的隨機(jī)性，但這一點(diǎn)對(duì)性能測試的結(jié)果應(yīng)該沒有太大影響）

  1. #include <iostream>   
  2. #include <cstdlib>  
  3. #include <ctime>  
  4. using namespace std;   
  5.   
  6. int f1(unsigned int num);  
  7. int f2(unsigned int num);  
  8. int f3(unsigned int num);  
  9. int f4(unsigned int num);  
  10. int f5(unsigned int num);  
  11.   
  12. void correctness_test();  
  13. void performance_test();  
  14. void prepare_test_data(unsigned int data[], int size);  
  15.   
  16. int main() {  
  17.     correctness_test();  
  18.     performance_test();  
  19.     return 0;   
  20. }  
  21.   
  22. int f1(unsigned int num) {  
  23.     int count = 0;  
  24.     while(num) {  
  25.         if(num & 1) ++count;  
  26.         num >>= 1;  
  27.     }  
  28.     return count;  
  29. }  
  30.   
  31. int f2(unsigned int num) {  
  32.     const unsigned int M1 = 0x55555555;  
  33.     const unsigned int M2 = 0x33333333;  
  34.     const unsigned int M4 = 0x0f0f0f0f;  
  35.     const unsigned int M8 = 0x00ff00ff;  
  36.     const unsigned int M16 = 0x0000ffff;  
  37.   
  38.     num = (num & M1) + ((num >> 1) & M1);  
  39.     num = (num & M2) + ((num >> 2) & M2);  
  40.     num = (num & M4) + ((num >> 4) & M4);  
  41.     num = (num & M8) + ((num >> 8) & M8);  
  42.     num = (num & M16) + ((num >> 16) & M16);  
  43.     return num;  
  44. }  
  45.   
  46. int f3(unsigned int num) {  
  47.     int count = 0;  
  48.     while(num) {  
  49.         num &= (num - 1);  
  50.         ++count;  
  51.     }  
  52.     return count;  
  53. }  
  54.   
  55. int f4(unsigned int num) {  
  56.     int count = 0;  
  57.     while(num) {  
  58.         int n;  
  59.         __asm {  
  60.             bsr eax, num  
  61.             mov n, eax  
  62.         }  
  63.         ++count;  
  64.         num ^= (1 << n);  
  65.     }  
  66.     return count;  
  67. }  
  68.   
  69. int f5(unsigned int num) {  
  70.     static const signed char TABLE[256] = {   
  71.         0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,  
  72.         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
  73.         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
  74.         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  75.         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
  76.         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  77.         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  78.         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
  79.         1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
  80.         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  81.         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  82.         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
  83.         2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
  84.         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
  85.         3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
  86.         4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8  
  87.     };  
  88.   
  89.     unsigned char* p = reinterpret_cast<unsigned char*>(&num);  
  90.     int count = 0;  
  91.     while(p != reinterpret_cast<unsigned char*>(&num + 1)) {  
  92.         count += TABLE[*p++];         
  93.     }  
  94.     return count;  
  95. }  
  96.   
  97. void correctness_test() {  
  98.     unsigned int test_data[] = {0, 1, 2, 3, 0x01234567, 0x89abcdef, 0xffffffff};  
  99.     unsigned int corect_result[] = {0, 1, 1, 2, 12, 20, 32};  
  100.   
  101.     int (*fn[])(unsigned int) = {f1, f2, f3, f4, f5};  
  102.     for(int i = 0; i < sizeof(fn) / sizeof(*fn); ++i) {  
  103.         for(int j = 0; j < sizeof(test_data) / sizeof(*test_data); ++j) {  
  104.             if(fn[i](test_data[j]) != corect_result[j]) {  
  105.                 cout << "f" << (i + 1) << " failed!" << endl;  
  106.                 exit(-1);  
  107.             }  
  108.         }  
  109.     }  
  110.     cout << "All methods passed correctness test." << endl;  
  111. }  
  112.   
  113. void performance_test() {  
  114.     const int TEST_DATA_SIZE = 100000000;  
  115.     unsigned int* test_data = new unsigned int[TEST_DATA_SIZE];  
  116.     prepare_test_data(test_data, TEST_DATA_SIZE);  
  117.   
  118.     int (*fn[])(unsigned int) = {f1, f2, f3, f4, f5};  
  119.     for(int i = 0; i < sizeof(fn) / sizeof(*fn); ++i) {  
  120.         clock_t start = clock();  
  121.         for(int j = 0; j < TEST_DATA_SIZE; ++j) {  
  122.             fn[i](test_data[j]);  
  123.         }  
  124.         int ticks = clock() - start;  
  125.         double seconds = ticks * 1.0 / CLOCKS_PER_SEC;  
  126.   
  127.         cout << "f" << (i + 1) << " consumed " << seconds << " seconds." << endl;  
  128.     }  
  129.     delete[] test_data;  
  130. }  
  131.   
  132. void prepare_test_data(unsigned int* data, int len) {  
  133.     srand(0);  
  134.     for(int i = 0; i < len; ++i) {  
  135.         data[i] = static_cast<unsigned int>(rand() * 1.0 / RAND_MAX * 0xffffffff);  
  136.     }  
  137. }  

在我的機(jī)器上（AMD Phenom 8560處理器，Windows XP SP2），使用Visual C++ 2008 Express Edition編譯并運(yùn)行（Release版），某一次得到的輸出如下：

All methods passed correctness test.

f1 consumed 14.156 seconds.

f2 consumed 1.032 seconds.

f3 consumed 4.656 seconds.

f4 consumed 13.687 seconds.

f5 consumed 1.422 seconds.

從結(jié)果來看，最慢的是第一種“逐位測試法”，最快的是第二種“分組統(tǒng)計(jì)法”。兩者相差近14倍！

第三種“循環(huán)減一相與法”表現(xiàn)也很不錯(cuò)，雖然跟最快的相比遜色很多，但比最慢的強(qiáng)多了；

第四種“匯編嵌入法”，表面上看，其復(fù)雜度是跟數(shù)值中1的位數(shù)相關(guān)，這一點(diǎn)與方法三一樣。而不像方法一那樣復(fù)雜度跟整個(gè)數(shù)的位數(shù)有關(guān)。但其表現(xiàn)并不令人滿意，結(jié)果幾乎跟方法一一樣差，而無法跟方法三相比。查了一下指令手冊(cè)，發(fā)現(xiàn)BSR指令并不是一條固定周期的指令，作用于32位整數(shù)時(shí)，快的時(shí)候它只需幾個(gè)CPU時(shí)鐘周期，慢的時(shí)候需要40幾個(gè)時(shí)鐘周期，我想它極有可能是在CPU內(nèi)部通過類似于“逐位查找”的微命令實(shí)現(xiàn)的。

第五種“查表法”的表現(xiàn)倒讓人相當(dāng)滿意，性能逼近方法二。注意我只用了基于字節(jié)編碼的表，如果實(shí)際使用中需要這種運(yùn)算，我們完全可以構(gòu)造一個(gè)基于unsigned short編碼的表，這樣一個(gè)表將占用64K內(nèi)存，在現(xiàn)代PC上仍屬小菜一碟，而每個(gè)32位數(shù)只需要把前后兩半查表的結(jié)果一加即可。那樣一來，其性能會(huì)不會(huì)比方法二還要強(qiáng)呢？有興趣的朋友可以試試。：P

最后，或許有朋友會(huì)問：第四種方法中既然采用嵌入?yún)R編，為何不把整個(gè)函數(shù)都用匯編來寫呢？那樣或許效率還會(huì)好一些。但那對(duì)其它幾種方法來說是不公平的，因?yàn)樗械姆椒ǘ伎梢愿挠脜R編來寫。所以，在這個(gè)函數(shù)中我只是把依賴于特定處理器（X86）、且無法使用C++語言及其標(biāo)準(zhǔn)庫直接實(shí)現(xiàn)的部分用匯編實(shí)現(xiàn)，其它的計(jì)算仍然用C++語言寫出。剩下的事情，跟其它幾種方法的實(shí)現(xiàn)一樣——讓編譯器看著辦吧，它愛怎么優(yōu)化就怎么優(yōu)化。

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類似文章 更多