专栏首页小樱的经验随笔C/C++中__builtin_popcount()的使用及原理

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

__builtin_popcount()用于计算一个 32 位无符号整数有多少个位为1

Counting out the bits     可以很容易的判断一个数是不是2的幂次:清除最低的1位(见上面)并且检查结果是不是0.尽管如此,有的时候需要直到有多少个被设置了,这就相对有点难度 了。

    GCC有一个叫做__builtin_popcount的内建函数,它可以精确的计算1的个数。尽管如此,不同于__builtin_ctz,它并没有被 翻译成一个硬件指令(至少在x86上不是)。相反的,它使用一张类似上面提到的基于表的方法来进行位搜索。这无疑很高效并且非常方便。

    其他语言的使用者没有这个选项(尽管他们可以重新实现这个算法)。如果一个数只有很少的1的位,另外一个方法是重复的获取最低的1位,并且清除它。

查看引用来源

为了在 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;     for (int i = 0; i <= 1000; i ++)         {         int k = popcount (i);         cout << k << " ";         }     cout << endl;     // 比较速度         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;

    start = clock ();     for (int i = 0; i < test; i ++)         {         popcount (i);         }     finish = clock ();     cout << (double)(finish - start) / (double)(CLOCKS_PER_SEC) << " s" << endl;

    start = clock ();     for (int i = 0; i < test; i ++)         {         //__builtin_popcount (i);    // G++内建函数, Dev-C++ 可支持         }     finish = clock ();     cout << (double)(finish - start) / (double)(CLOCKS_PER_SEC) << " s" << endl;     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 from -10 to 10. You task is to Go from the top-left corner (1, 1) to the bottom-right corner (M, N). You can only move right or down, and you can not go out of the matrix. The number in the grid you passed must be 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 0 0 0 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> using namespace std;

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)); }

int main () ...{     while (scanf ("%d%d", &m, &n) != EOF)         ...{         f ();         }     return 0; }

提交结果: 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, 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, 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, 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, 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, 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, 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, 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添加======================== 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; } 这个二分法的原理: 用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。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • UESTC 1584 Washi与Sonochi的约定【树状数组裸题+排序】

    题目链接:UESTC 1584 Washi与Sonochi的约定 题意:在二维平面上,某个点的ranked被定义为x坐标不大于其x坐标,且y坐标不大于其y坐标的...

    Angel_Kitty
  • ex_gcd(个人模版)

    ex_gcd: 1 #include<stdio.h> 2 #include<string.h> 3 using namespace std; 4 in...

    Angel_Kitty
  • NYOJ 题目77 开灯问题(简单模拟)

    开灯问题 时间限制:3000 ms  |            内存限制:65535 KB 难度:1 描述 有n盏灯,编号为1~n,第1个人把所有灯打开,第2个...

    Angel_Kitty
  • loj#2542. 「PKUWC2018」随机游走(MinMax容斥 期望dp)

    设\(f[i][sta]\)表示从\(i\)到集合\(sta\)中任意一点的最小期望步数

    attack
  • 洛谷P4781 【模板】拉格朗日插值(拉格朗日插值)

    \[f(x) = \sum_{i = 1}^n y_i \prod_{j \not = i} \frac{k - x[j]}{x[i] - x[j]}\]

    attack
  • AtCoder Beginner Contest 103

    首先我们发现,对于每个$a_i$,我们都可以构造一个数使得$x \pmod {a_i} = a_i - 1$

    attack
  • 剑指offer 和为s的两个数字

    输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

    week
  • 浙大版《C语言程序设计(第3版)》题目集 练习5-2 找两个数中最大者

    C you again 的博客
  • 2006北京市小学生程序设计友谊赛详细答案

    分析: 祖冲之密率355/113是圆周率pi的近似值。 注意: 本题第一个输入输出样例有误。输入为4时,输出应为5。 算法实现:

    海天一树
  • C语言生成固定范围的随机数

    本文为仙士可原创文章,转载无需和我联系,但请注明来自仙士可博客www.php20.cn

    仙士可

扫码关注云+社区

领取腾讯云代金券