如何只使用位运算符来实现位计数？ [英] How to implement Bitcount using only Bitwise operators?

问题描述

的任务是实现仅使用位操作一个比特计数逻辑。我得到它做工精细，但我想，如果有人能提出一个更优雅的方式。

The task is to implement a bit count logic using only bitwise operators. I got it working fine, but am wondering if someone can suggest a more elegant approach.

只有按位老年退休金计划是允许的。没有如果，对等。

Only Bitwise ops are allowed. No "if", "for" etc

int x = 4;

printf("%d\n", x & 0x1);
printf("%d\n", (x >> 1) & 0x1);
printf("%d\n", (x >> 2) & 0x1);
printf("%d\n", (x >> 3) & 0x1);

感谢您。

推荐答案

从<一个href=\"http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel\">http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here

c = v - ((v >> 1) & 0x55555555);
c = ((c >> 2) & 0x33333333) + (c & 0x33333333);
c = ((c >> 4) + c) & 0x0F0F0F0F;
c = ((c >> 8) + c) & 0x00FF00FF;
c = ((c >> 16) + c) & 0x0000FFFF;

编辑：不可否认这是优化了一下，这使得它难以阅读。它更容易为已读：

Admittedly it's a bit optimized which makes it harder to read. It's easier to read as:

c = (v & 0x55555555) + ((v >> 1) & 0x55555555);
c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
c = (c & 0x0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F);
c = (c & 0x00FF00FF) + ((c >> 8) & 0x00FF00FF);
c = (c & 0x0000FFFF) + ((c >> 16)& 0x0000FFFF);

这五个的每一个步骤，在第1组增加相邻位一起，然后如图2所示，然后4等
该方法是基于分而治之。

Each step of those five, adds neighbouring bits together in groups of 1, then 2, then 4 etc. The method is based in divide and conquer.

在第一步，我们加在一起位0和1，并把结果在这两个位段0-1，加2和3位，并把结果在这两个位段2-3等...

In the first step we add together bits 0 and 1 and put the result in the two bit segment 0-1, add bits 2 and 3 and put the result in the two-bit segment 2-3 etc...

在第二步骤中，我们添加两个比特0-1和2-3在一起并把结果在四比特0-3，添加在一起的两个比特4-5和6-7，并把结果四位4-7等...

In the second step we add the two-bits 0-1 and 2-3 together and put the result in four-bit 0-3, add together two-bits 4-5 and 6-7 and put the result in four-bit 4-7 etc...

例如：

So if I have number 395 in binary 0000000110001011 (0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1)
After the first step I have:      0000000101000110 (0+0 0+0 0+0 0+1 1+0 0+0 1+0 1+1) = 00 00 00 01 01 00 01 10
In the second step I have:        0000000100010011 ( 00+00   00+01   01+00   01+10 ) = 0000 0001 0001 0011
In the fourth step I have:        0000000100000100 (   0000+0001       0001+0011   ) = 00000001 00000100
In the last step I have:          0000000000000101 (       00000001+00000100       )

，它等于5，这是正确的结果

which is equal to 5, which is the correct result

这篇关于如何只使用位运算符来实现位计数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！