C/C++中__builtin_popcount()的使用及原理

__builtin_popcount()用于計算一個 32 位無符号整數有多少個位為1

Counting out the bits

可以很容易的判斷一個數是不是2的幂次：清除最低的1位（見上面）并且檢查結果是不是0.盡管如此，有的時候需要直到有多少個被設定了，這就相對有點難度

了。

GCC有一個叫做__builtin_popcount的内建函數，它可以精确的計算1的個數。盡管如此，不同于__builtin_ctz，它并沒有被

翻譯成一個硬體指令（至少在x86上不是）。相反的，它使用一張類似上面提到的基于表的方法來進行位搜尋。這無疑很高效并且非常友善。

檢視引用來源

為了在 VC 上實作 __builtin_popcount (unsigned u) 的功能，自己寫了兩個函數，分别是 popcnt

(unsigned u)， popcount (unsigned u) 。

前者是通過清除 u 最低的 bit 1 ，直至 u 為 0 ，每次都為計數器加 1 。時間複雜度為 O (m) ， m 為 bit 1 的個數。

後者是使用二分法，比較巧妙，跟蹤調試一下就知道原理了。時間複雜度為 O (lg N) , N 為位數。

不過最高效的還是使用查表的方式來計算。

但是需要弄一個很大的表，不然随着位數的增長，查表的速度還是比不上二分法的速度。例如 64 位整數，儲存 所有 8 位整數的結果 （256

個）。查表需要操作 8 次，而二分法需要 6 次而已。

// 計算一個 32 位無符号整數有多少個位為 1

#include <iostream>

#include <ctime>

using namespace std;

unsigned popcnt (unsigned u)

{

    unsigned ret = 0;

    while (u)

        {

        u = (u & (u - 1));    // 将 u 最右邊的 1 清除

        ret ++;

        }

    return ret;

}

unsigned popcount (unsigned u)

    u = (u & 0x55555555) + ((u >> 1) & 0x55555555);

    u = (u & 0x33333333) + ((u >> 2) & 0x33333333);

    u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);

    u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);

    u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);

    return u;

int main ()

     // 先測試一下函數是否正常工作

    for (int i = 0; i <= 1000; i ++)

        int k = popcnt (i);

        cout << k << " ";

    cout << endl;

        int k = popcount (i);

    // 比較速度    

    int test;

    test = (1U << 31) - 1;

    //test = 1000000;

    clock_t start, finish;

    start = clock ();

    for (int i = 0; i < test; i ++)

        popcnt (i);

    finish = clock ();

    cout << (double)(finish - start) / (double)(CLOCKS_PER_SEC)

<< " s" << endl;

        popcount (i);

        //__builtin_popcount (i);    // G++内建函數， Dev-C++ 可支援

    system ("pause");

    return 0;

/*

使用 VC 2005 ，在 test = (1U << 31) - 1 時， release 狀态是 0 s 出結果的，但是

debug 狀态就很慢， 換 test = 1000000 試試。

使用其他 IDE， 即使是 release 狀态下，速度也不理想。但是可以測得 __builtin_popcount （通過查表來計算）比較快。

*/

說到底，這個函數到底有什麼實際用處呢？當然有了，使用一個二進制數字表示一個集合的時候，枚舉一個組合（子集），需要判斷這個數字裡面的 1

的個數是不是和子集的大小相等。這種方法通常是屬于暴力法，如果不是使用二進制數字表示集合，很可能就計算逾時了。

下面有個例子（sicily 1158），期待更好的解法，但是暴力法的效果還不錯^_^而且實作簡單。。

====================================帥氣的分割

線====================================

Pick numbers

Total Submit : 371    Accepted Submit : 135

Problem

Given a matrix of size M*N, the elements of which are integer numbers

the top-left corner (1, 1) to the bottom-right corner (M, N). You can

only move right or down, and you can

picked. The sum of numbers you picked must

be positive and as minimal as possible.

Input

The input contains several test cases.

      The first line of each test case are two integer numbers M, N

(2<=M<=10, 2<=N<=10), indicating the number

      of rows and columns of the matrix. The following M lines, each

contains N integer numbers.

Output

For each test case, output the sum of numbers you picked on a single

line. If you can't get a positive sum,

output -1.

Sample input

2 2

0 2

1 0

3 3

0 0 0

Sample output

1

-1

Problem Source

2006 Algorithm Course Examination

====================================無聊的分割

分析：

用一個二進制數字 path 表示所走的路徑，從低位開始，如果某位為 1 ，表示向下走，否則向右走。

path 中的位 1 必須有 m - 1 個，使用 G++ 内建函數 __builtin_popcount (path) 來計算。

path 的起始值為 first = (1 << (m - 1)) - 1 ，表示先向下走 m - 1 步。

path 的終止值為 last = first << (n - 1) ，表示先向右走 n - 1 步。

從 first 到 last ，枚舉所有可行的 path ，然後計算對應的 sum ，目标是找一個最小的 sum > 0 ，

如果找不到，sum = -1 。

注意此題不能用動态規劃來求最小值，因為該最小值可能是負數。

枚舉的次數是 2m + n - 2 - 2n - 1， 當 m, n <= 10 時為 512 。

#include <cstdio>

const int M = 10;

const int N = 10;

int d [M] [N];

int m, n;

void f ()

...{

    for (int i = 0; i < m; i ++)

        ...{

        for (int j = 0; j < n; j ++)

            ...{

            scanf ("%d", &d [i] [j]);

            }

    int first = (1 << (m - 1)) - 1;

    int last = first << (n - 1);

    int cnt = m - 1;

    int MASK = 1 << (m + n - 2);

    int max = (1U << 31) - 1;

    for (int path = first; path <= last; path ++)

        if (__builtin_popcount (path) == cnt)

            int sum = d [0] [0];

            for (int i = 0, j = 0, mask = 1; mask < MASK; mask

<<= 1)

                ...{

                if (mask & path)

                    ...{

                    i ++;                   

                    } else    ...{

                        j ++;

                        }

                sum += d [i] [j];

                }

            if (sum > 0 && sum < max)

                max = sum;

    printf ("%d ", (max == ((1U << 31) - 1) ? -1 : max));

    while (scanf ("%d%d", &m, &n) != EOF)

        f ();

送出結果：

Run ID      User Name      Problem      Language      Status     

Run Time      Run Memory      Submit Time

84848       rappizit     1158     C++     Accepted     0.01 sec    

260 KB     2007-09-17 13:38:57

===================================遺忘的分割

線=====================================

以下内容為新添加的：

經測試，該函數的速度是 G++ 的一半，是以有理由認為 G++ 儲存的表的大小是 65536

的（或者使用彙編）。但是不可能在自己的代碼裡面加上那麼一大段資料吧？權衡一下，表的大小設為 256 是适當的，可以在 VC 裡面使用以下代碼。

char poptable [256] =

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8

};

unsigned __builtin_popcount (unsigned u)

    return poptable [u & 0xFF] + poptable [(u >> 8) &

0xFF] + poptable [(u >> 16) & 0xFF] + poptable [(u >>

24) & 0xFF];

}=====================20080725添加========================

這個二分法的原理：

用8位二進制數來做示範好了，例如 u = 10110011。

10110011

00010001    //每兩位取1位，即取偶數位, u & 01010101

01010001    //取奇數位并右移一位, (u >> 1) & 01010101

---------------

01100010    //上面兩數相加，指派給u，注意每兩列相加的結果不會進位到第三列

00100010    //每四位取低兩位， u & 00110011

00010000    //每四位取高兩位并右移兩位, (u >> 2) & 00110011

00110010    //上面兩數相加，指派給u

00000010    //每八位取低四位， u & 00001111

00000011    //每八位取高四位并右移四位，(u >> 4) & 00001111

00000101    //上面兩數相加，指派給u

最終結果 u = 5。