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 }