count number of set bits in integer
Question
i am studing different methods about bit counting ,or population count methods fopr given integer, during this days,i was trying to figure out how following algorithms works
pop(x)=-sum(x<<i) where i=0:31
i think that after calculate each value of x,we will get
x+2*x+4*x+8*x+16*x+..............+2^31*x =4294967294*x
if we multiply it by -1,we get -4294967294*x
,but how it counts number of bits?please help me to understand this method well.thanks
Solution
I believe you mean
as seen in the cover of the book Hacker's Delight, where the symbol means left-rotation not left-shift which will produce the wrong results and downvotes.
This method works because the rotation will cause all binary digits of x to appear in every possible bits in all terms, and because of 2's complement.
Take a simpler example. Consider numbers with only 4 binary digits, where the digits can be represented as ABCD
, then the summation means:
ABCD // x <<rot 0
+ BCDA // x <<rot 1
+ CDAB // x <<rot 2
+ DABC // x <<rot 3
We note that every column has all of A, B, C, D. Now, ABCD
actually means "2³ A + 2² B + 2¹ C + 2⁰ D", so the summation is just:
2³ A + 2² B + 2¹ C + 2⁰ D
+ 2³ B + 2² C + 2¹ D + 2⁰ A
+ 2³ C + 2² D + 2¹ A + 2⁰ B
+ 2³ D + 2² A + 2¹ B + 2⁰ C
——————————————————————————————————————————————————————
= 2³(A+B+C+D) + 2²(B+C+D+A) + 2¹(C+D+A+B) + 2⁰(D+A+B+C)
= (2³ + 2² + 2¹ + 2⁰) × (A + B + C + D)
The (A + B + C + D) is the population count of x and (2³ + 2² + 2¹ + 2⁰) = 0b1111 is -1 in 2's complement, so the summation is the negative of the population count.
The argument can be easily extended to 32-bit numbers.
OTHER TIPS
#include <stdio.h>
#include <conio.h>
unsigned int f (unsigned int a , unsigned int b);
unsigned int f (unsigned int a , unsigned int b)
{
return a ? f ( (a&b) << 1, a ^b) : b;
}
int bitcount(int n) {
int tot = 0;
int i;
for (i = 1; i <= n; i = i<<1)
if (n & i)
++tot;
return tot;
}
int bitcount_sparse_ones(int n) {
int tot = 0;
while (n) {
++tot;
n &= n - 1;
}
return tot;
}
int main()
{
int a = 12;
int b = 18;
int c = f(a,b);
printf("Sum = %d\n", c);
int CountA = bitcount(a);
int CountB = bitcount(b);
int CntA = bitcount_sparse_ones(a);
int CntB = bitcount_sparse_ones(b);
printf("CountA = %d and CountB = %d\n", CountA, CountB);
printf("CntA = %d and CntB = %d\n", CntA, CntB);
getch();
return 0;
}