BitCountTest.java

import java.util.Vector;
import java.util.Random;

class BitCountTest {
  // From Java 1.5+
  public static int bitCountJava(int i) {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
  }

  // From Brian
  public static int bitCountBrian(int i) {
    i = i - ((i >>> 1) & 0xdb6db6db) - ((i >>> 2) & 0x49249249);
    i = (i + (i >>> 3)) & 0xc71c71c7;
    i = i + (i >>> 6);
    i = i + (i >>> 12) + (i >>> 24);
    return i & 0x3f;
  }

  public static void doTest(int num, int passes) {
    Random generator = new Random();
    long nsecs_java = 0;
    long nsecs_brian = 0;

    // Make a vector of num random ints
    Vector<Integer> data = new Vector<Integer>(num);
    Vector<Integer> results_java = new Vector<Integer>(num);
    Vector<Integer> results_brian = new Vector<Integer>(num);
    for (int i=0; i<num; ++i) {
      data.add(generator.nextInt());
      results_java.add(0);
      results_brian.add(0);
    }

    for (int pass=0; pass < passes; ++pass) {
      // Count the bits the old way (and time it)
      long start = System.nanoTime();
      for (int i=0; i<num; ++i) {
        results_java.set( i, bitCountJava(data.get(i)) );
      }
      nsecs_java += (System.nanoTime() - start);

      // Count the bits the new way (and time it)
      start = System.nanoTime();
      for (int i=0; i<num; ++i) {
        results_brian.set( i, bitCountBrian(data.get(i)) );
      }
      nsecs_brian += (System.nanoTime() - start);

      for (int i=0; i<num; ++i) {
        // Explode if they don't match
        if (results_brian.get(i) != results_java.get(i)) {
          System.err.println("Results do not match!");
          System.err.println("bitCountJava(" + i + ") = " + results_java.get(i));
          System.err.println("bitCountBrian(" + i + ") = " + results_brian.get(i));
          System.exit(1);
        }
      }
      System.out.print(".");
    }

    // Report the results
    System.out.println("");
    System.out.println("bitCountJava avg: " + (nsecs_java / num / passes) + " ns");
    System.out.println("bitCountBrian avg: " + (nsecs_brian / num / passes) + " ns");
  }

  public static void main(String args[]) { 
    doTest(2000000, 200);
  }
}