Count Bits
by Isai Damier, Android Engineer @ Google

/****************************************************************************
 * Author: Isai Damier
 * Title: Count Bits
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Count the number of 1s in the given bit sequence.
 *
 * Sample Input: integer representation of bit sequence 1000110010
 * Sample Output: 4
 *
 * Technical Details: Mumerous techniques have been devised to
 *    count the number of bits in a bit sequence. The simplest way
 *    to internalize why a given technique works is to take a
 *    pencil and run though a few examples.
 *
 *    The presented approach runs through a loop and clears the
 *    lowest set bit of n during each iteration. When no set bit
 *    is left (i.e. n==0) the number of iterations is returned.
 *
 *    0] Set count to 0
 *    1] while n > 0:
 *     -- clear the least significant bit in n: n &= (n-1)
 *     -- increment count by 1: count++
 *    2] return count.
 *
 *  Alternate Algorithm: e.g. n = n & ~(n & ~(n-1));
 ***************************************************************************/ 
 public int countBits(int n) {
  if (0 == n) {
    return n;
  }
  int count = 0;
  while (0 != n) {
    n &= (n - 1);
    count++;
  }
  return count;
}

import org.junit.Test;
import static org.junit.Assert.*;

public class BitwiseTest {

  /**
   * Test of countBits method, of class Bitwise.
   */
  @Test
  public void testCountBits() {
    System.out.println(""countBits"");
    Bitwise bits = new Bitwise();
    String[] set = {""0000000000"", ""0000001000"", ""0001010000"",
      ""1100001000"", ""1000110010"", ""0101110001"", ""1100101101"",
      ""1101110101"", ""1101111011"", ""1111101111"", ""1111111111""};

    for (int i = 0; i < set.length; i++) {
      assertEquals(i, bits.countBits(Integer.parseInt(set[i], 2)));
    }
  }

}