Question: Count number of bits and do it in O(1)

Solution: private static int bitCount(long val) {
val -= (val & 0xaaaaaaaaaaaaaaaaL) >>> 1;
val = (val & 0x3333333333333333L) + ((val >>> 2) & 0x3333333333333333L);
val = (val + (val >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
val += val >>> 8;
val += val >>> 16;
return ((int)(val) + (int)(val >>> 32)) & 0xff;
}