bitcnts.c

/*
**  BITCNTS.C - Test program for bit counting functions
**
**  public domain by Bob Stout & Auke Reitsma
*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <limits.h>
#include <time.h>
#include <float.h>
#include "bitops.h"

#define ITERS  1500000L
#define FUNCS  8

static int CDECL bit_shifter(long int x);

int main(void)
{
      clock_t start, stop;
      double ct, cmin = DBL_MAX, cmax = 0;
      int i, cminix, cmaxix;
      long j, n;
      static int (* CDECL pBitCntFunc[FUNCS])(long) = {
            bit_count,
            bitcount,
            ntbl_bitcnt,
            ntbl_bitcount,
            btbl_bitcnt,
            BW_btbl_bitcount,
            AR_btbl_bitcount,
            bit_shifter
      };
      static char *text[FUNCS] = {
            "Optimized 1 bit/loop counter",
            "Ratko's mystery algorithm",
            "Recursive bit count by nybbles",
            "Non-recursive bit count by nybbles",
            "Recursive bit count by bytes",
            "Non-recursive bit count by bytes (BW)",
            "Non-recursive bit count by bytes (AR)",
            "Shift and count bits"
      };

      puts("Bit counter algorithm benchmark\n");

      for (i = 0; i < FUNCS; i++)
      {
            start = clock();

            for (j = n = 0; j < ITERS; j++)
                  n += pBitCntFunc[i](j);

            stop = clock();
            ct = (stop - start) / (double)CLOCKS_PER_SEC;
            if (ct < cmin)
            {
                  cmin = ct;
                  cminix = i;
            }
            if (ct > cmax)
            {
                  cmax = ct;
                  cmaxix = i;
            }

            printf("%-38s> Time: %7.3f sec.; Bits: %ld\n", text[i], ct, n);
      }
      printf("\nBest  > %s\n", text[cminix]);
      printf("Worst > %s\n", text[cmaxix]);
      return 0;
}

static int CDECL bit_shifter(long int x)
{
      int i, n;

      for (i = n = 0; x && (i < (sizeof(long) * CHAR_BIT)); ++i, x >>= 1)
            n += (int)(x & 1L);
      return n;
}