nicer formatting
[tridge/junkcode.git] / bitcount.c
1 typedef unsigned uint32;
2
3 static inline int bcount1(uint32 x)
4 {
5         int count=0;
6         int i;
7         for (i=0;i<32;i++)
8                 if (x & (1<<i)) count++;
9         return count;
10 }
11
12 static inline int bcount2(uint32 x)
13 {
14         int count;
15         for (count=0; x; count++)
16                 x &= (x-1);
17         return count;
18 }
19
20
21 static int pop_count[256];
22
23 static void init_eval_tables(void)
24 {
25         int i;
26
27         for (i=0;i<256;i++) {
28                 int j, ret=0;
29                 for (j=0;j<8;j++)
30                         if (i & (1<<j))
31                                 ret++;
32                 pop_count[i] = ret;
33         }
34 }
35
36 static inline int pop_count16(uint32 x)
37 {
38         return pop_count[(x)&0xFF] + pop_count[((x)>>8)&0xFF];
39 }
40
41 static inline int pop_count32(uint32 x)
42 {
43         return pop_count16((x) & 0xFFFF) + pop_count16((x) >> 16);
44 }
45
46 int main(void)
47 {
48         int i;
49         uint32 x;
50
51         init_eval_tables();
52
53         for (i=0;i<1000000;i++) {
54                 x = random();
55                 if (pop_count32(x) != bcount1(x))
56                         printf("x=%x\n", x);
57         }
58
59         return 0;
60 }