package com.interview.bits;

/**
 * http://www.geeksforgeeks.org/count-set-bits-in-an-integer/
 */
public class CountBits {

    public CountBits(){
        preCalculate();
    }
    public int countBits(int num){
        int count=0;
        while(num > 0){
            num &= num-1;
            count++;
        }
        return count;
    }
    
    private int count[] = new int[256];
    
    void preCalculate(){
        for(int i=0; i < 256; i++){
            count[i] = countBits(i);
        }
    }
    
    public int countBitsFaster(int num){
        //get 8 bits at a time and check count from count array
        int total = 0;
        int mask = (1<<8) - 1;
        for(int i=0 ; i < 4; i++){
            total += count[num & mask];
            num = num>>>8;
        }
        return total;
    }
    public static void main(String args[]){
        CountBits cb = new CountBits();
        System.out.println(cb.countBits(3636363));
        System.out.println(cb.countBitsFaster(3636363));
    }
}

@@ -797,32 +797,513 @@
 rn total;%0A    %7D%0A
+    %0A    //http://bits.stephan-brumme.com/countBits.html%0A    public int countBitsEvenFaster(int x)%7B%0A        // count bits of each 2-bit chunk%0A        x = x - ((x %3E%3E 1) & 0x55555555);%0A        // count bits of each 4-bit chunk%0A        x = (x & 0x33333333) + ((x %3E%3E 2) & 0x33333333);%0A        // count bits of each 8-bit chunk%0A        x = x + (x %3E%3E 4);%0A        // mask out junk%0A        x &= 0xF0F0F0F;%0A        // add all four 8-bit chunks%0A        return (x * 0x01010101) %3E%3E 24;%0A    %7D%0A%0A
     public stati
@@ -1474,20 +1474,81 @@
 (3636363));%0A
+        System.out.println(cb.countBitsEvenFaster(3636363));%0A
     %7D%0A%7D%0A

add one new method