bitcount.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <sys/time.h>

static double getdiff(const struct timeval &t1, const struct timeval &t2)
{
  return (t2.tv_sec - t1.tv_sec) + 1.0 * (t2.tv_usec - t1.tv_usec) / 1000000;
}

int dummy(int t)
{
  return 0;
}

int popcount1(unsigned int bits)
{
  int c = 0;
  while(bits){
    if(bits & 1) c++;
    bits = bits >> 1;
  }
  return c;
}

int popcount2(unsigned int bits)
{
  int c = 0;
  while(bits){
    c++;
    bits &= bits - 1;
  }
  return c;
}

int popcount3(unsigned int bits)
{
  bits = (bits & 0x55555555) + ((bits & 0xaaaaaaaa) >>  1);
  bits = (bits & 0x33333333) + ((bits & 0xcccccccc) >>  2);
  bits = (bits & 0x0f0f0f0f) + ((bits & 0xf0f0f0f0) >>  4);
  bits = (bits & 0x00ff00ff) + ((bits & 0xff00ff00) >>  8);
  return (bits & 0x0000ffff) + ((bits & 0xffff0000) >> 16);
}

int main()
{
  struct timeval t1, t2;
  const int maxloop = 100000000;
  double basetime;
  int i;
  volatile int ret;
  
  gettimeofday(&t1, NULL);
  for(i=0;i<maxloop;i++){
    ret = i;
  }
  gettimeofday(&t2, NULL);
  basetime = getdiff(t1, t2);

  gettimeofday(&t1, NULL);
  for(i=0;i<maxloop;i++){
    ret = __builtin_popcount(0xaaaaaaaa);
  }
  gettimeofday(&t2, NULL);
  printf("__builtin_popcount(0xaaaaaaaa)=%d: %10.6f sec\n", ret, getdiff(t1, t2) - basetime);

  gettimeofday(&t1, NULL);
  for(i=0;i<maxloop;i++){
    ret = __builtin_popcount(0x00000001);
  }
  gettimeofday(&t2, NULL);
  printf("__builtin_popcount(0x00000001)=%d: %10.6f sec\n", ret, getdiff(t1, t2) - basetime);

  gettimeofday(&t1, NULL);
  for(i=0;i<maxloop;i++){
    ret = __builtin_popcount(0x80000000);
  }
  gettimeofday(&t2, NULL);
  printf("__builtin_popcount(0x80000000)=%d: %10.6f sec\n", ret, getdiff(t1, t2) - basetime);

  gettimeofday(&t1, NULL);
  for(i=0;i<maxloop;i++){
    ret = popcount1(0xaaaaaaaa);
  }
  gettimeofday(&t2, NULL);
  printf("popcount1(0xaaaaaaaa)=%d: %10.6f sec\n", ret, getdiff(t1, t2) - basetime);

  gettimeofday(&t1, NULL);
  for(i=0;i<maxloop;i++){
    ret = popcount1(0x00000001);
  }
  gettimeofday(&t2, NULL);
  printf("popcount1(0x00000001)=%d: %10.6f sec\n", ret, getdiff(t1, t2) - basetime);

  gettimeofday(&t1, NULL);
  for(i=0;i<maxloop;i++){
    ret = popcount1(0x80000000);
  }
  gettimeofday(&t2, NULL);
  printf("popcount1(0x80000000)=%d: %10.6f sec\n", ret, getdiff(t1, t2) - basetime);

  gettimeofday(&t1, NULL);
  for(i=0;i<maxloop;i++){
    ret = popcount2(0xaaaaaaaa);
  }
  gettimeofday(&t2, NULL);
  printf("popcount2(0xaaaaaaaa)=%d: %10.6f sec\n", ret, getdiff(t1, t2) - basetime);

  gettimeofday(&t1, NULL);
  for(i=0;i<maxloop;i++){
    ret = popcount2(0x00000001);
  }
  gettimeofday(&t2, NULL);
  printf("popcount2(0x00000001)=%d: %10.6f sec\n", ret, getdiff(t1, t2) - basetime);

  gettimeofday(&t1, NULL);
  for(i=0;i<maxloop;i++){
    ret = popcount2(0x80000000);
  }
  gettimeofday(&t2, NULL);
  printf("popcount2(0x80000000)=%d: %10.6f sec\n", ret, getdiff(t1, t2) - basetime);

  gettimeofday(&t1, NULL);
  for(i=0;i<maxloop;i++){
    ret = popcount3(0xaaaaaaaa);
  }
  gettimeofday(&t2, NULL);
  printf("popcount3(0xaaaaaaaa)=%d: %10.6f sec\n", ret, getdiff(t1, t2) - basetime);

  gettimeofday(&t1, NULL);
  for(i=0;i<maxloop;i++){
    ret = popcount3(0x00000001);
  }
  gettimeofday(&t2, NULL);
  printf("popcount3(0x00000001)=%d: %10.6f sec\n", ret, getdiff(t1, t2) - basetime);

  gettimeofday(&t1, NULL);
  for(i=0;i<maxloop;i++){
    ret = popcount3(0x80000000);
  }
  gettimeofday(&t2, NULL);
  printf("popcount3(0x80000000)=%d: %10.6f sec\n", ret, getdiff(t1, t2) - basetime);

  return 0;
  
}