Artificial Idiot

count-number-of-ones-in-unsigned-integer

发表于

Count number of 1’s of unsigned integer in binary format

code snippet for counting number of 1’s of unsigned integer in binary format

1
2
3
4
5
6
7
8
9
#include <stdio.h>
#define BX_(x) ((x) - (((x)>>1)&0x77777777) - (((x)>>2)&0x33333333) - (((x)>>3)&0x11111111))
#define BITCOUNT(x) (((BX_(x) + (BX_(x)>>4)) & 0x0F0F0F0F) % 255)
int main()
{
    unsigned int x = 11;
    printf("number of 1's is %d\n", BITCOUNT(x));
}

What we know: $ \sum_{i=0}^{31} x_{i} \cdot 2^i $
What we want: $ \sum_{i=0}^{31} x_{i} $

Let’s define:
X1: (x>>1) &0x77777777
X2: (x>>2) &0x33333333
X3: (x>>3) &0x11111111

index X X1 X2 X3 X-X1-X2-X3
0 0 N/A N/A N/A 0
1 1 0 N/A N/A 0
2 2 1 0 N/A 0
3 3 2 1 0 0
4 4 N/A N/A N/A 4
5 5 4 N/A N/A 4
6 6 5 4 N/A 4
7 7 6 5 4 4
8 8 N/A N/A N/A 8
9 9 8 N/A N/A 8
10 10 9 8 N/A 8
11 11 10 9 8 8
12 12 N/A N/A N/A 12
13 13 12 N/A N/A 12
14 14 13 12 N/A 12
15 15 14 13 12 12
16 16 N/A N/A N/A 16
17 17 16 N/A N/A 16
18 18 17 16 N/A 16
19 19 18 17 16 16
20 20 N/A N/A N/A 20
21 21 20 N/A N/A 20
22 22 21 20 N/A 20
23 23 22 21 20 20
24 24 N/A N/A N/A 24
25 25 24 N/A N/A 24
26 26 25 24 N/A 24
27 27 26 25 24 24
28 28 N/A N/A N/A 28
29 29 28 N/A N/A 28
30 30 29 28 N/A 28
31 31 30 29 28 28

define
B = X - X1 - X2 - X3
$=(x_{0} + x_{1} + x_{2} + x_{3}) \cdot 2^0$
$+(x_{4} + x_{5} + x_{6} + x_{7}) \cdot 2^4$
$+(x_{8} + x_{9} + x_{10} + x_{11}) \cdot 2^8$
$+(x_{12} + x_{13} + x_{14} + x_{15}) \cdot 2^{12}$
$+(x_{16} + x_{17} + x_{18} + x_{19}) \cdot 2^{16}$
$+(x_{20} + x_{21} + x_{22} + x_{23}) \cdot 2^{20}$
$+(x_{24} + x_{25} + x_{26} + x_{27}) \cdot 2^{24}$
$+(x_{28} + x_{28} + x_{30} + x_{31}) \cdot 2^{28}$

Define
B_1 = B >> 4
$=(x_{4} + x_{5} + x_{6} + x_{7}) \cdot 2^0$
$+(x_{8} + x_{9} + x_{10} + x_{11}) \cdot 2^4$
$+(x_{12} + x_{13} + x_{14} + x_{15}) \cdot 2^8$
$+(x_{16} + x_{17} + x_{18} + x_{19}) \cdot 2^{12}$
$+(x_{20} + x_{21} + x_{22} + x_{23}) \cdot 2^{16}$
$+(x_{24} + x_{25} + x_{26} + x_{27}) \cdot 2^{20}$
$+(x_{28} + x_{28} + x_{30} + x_{31}) \cdot 2^{24}$

Define
B2 = B + B1
$=(x_{0} + x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7}) \cdot 2^0$
$+(x_{4} + x_{5} + x_{6} + x_{7} + x_{8} + x_{9} + x_{10} + x_{11}) \cdot 2^4$
$+(x_{8} + x_{9} + x_{10} + x_{11} + x_{12} + x_{13} + x_{14} + x_{15}) \cdot 2^8$
$+(x_{12} + x_{13} + x_{14} + x_{15} + x_{16} + x_{17} + x_{18} + x_{19}) \cdot 2^{12}$
$+(x_{16} + x_{17} + x_{18} + x_{19} + x_{20} + x_{21} + x_{22} + x_{23}) \cdot 2^{16}$
$+(x_{20} + x_{21} + x_{22} + x_{23} + x_{24} + x_{25} + x_{26} + x_{27}) \cdot 2^{20}$
$+(x_{24} + x_{25} + x_{26} + x_{27} + x_{28} + x_{28} + x_{30} + x_{31}) \cdot 2^{24}$
$+(x_{28} + x_{28} + x_{30} + x_{31}) \cdot 2^{28}$

Define
B3 = B2 & 0x0F0F0F0F
$B_3=(x_{0} + x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7}) \cdot 2^0$
$+(x_{8} + x_{9} + x_{10} + x_{11} + x_{12} + x_{13} + x_{14} + x_{15}) \cdot 2^8$
$+(x_{16} + x_{17} + x_{18} + x_{19} + x_{20} + x_{21} + x_{22} + x_{23}) \cdot 2^{16}$
$+(x_{24} + x_{25} + x_{26} + x_{27} + x_{28} + x_{28} + x_{30} + x_{31}) \cdot 2^{24}$

As we know $0 \leq \sum_{i=j}^{j+7} x_{i}\leq 8 $ and $ p\cdot 2^n \mod (2^n - 1) = p $

$B_3 \mod (2^8-1)$
$=(x_{0} + x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7}) \cdot 2^0 \mod (2^8-1)$
$+(x_{8} + x_{9} + x_{10} + x_{11} + x_{12} + x_{13} + x_{14} + x_{15}) \cdot 2^8 \mod (2^8-1)$
$+(x_{16} + x_{17} + x_{18} + x_{19} + x_{20} + x_{21} + x_{22} + x_{23}) \cdot 2^{16} \mod (2^8-1)$
$+(x_{24} + x_{25} + x_{26} + x_{27} + x_{28} + x_{28} + x_{30} + x_{31}) \cdot 2^{24} \mod (2^8-1)$

$=(x_{0} + x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7}) $
$+(x_{8} + x_{9} + x_{10} + x_{11} + x_{12} + x_{13} + x_{14} + x_{15}) $
$+(x_{16} + x_{17} + x_{18} + x_{19} + x_{20} + x_{21} + x_{22} + x_{23}) $
$+(x_{24} + x_{25} + x_{26} + x_{27} + x_{28} + x_{28} + x_{30} + x_{31}) $

$=\sum_{i=0}^{31} x_{i} $
This is what we want!