java - How to count the number of 1's a number will have in binary? -

possible duplicate:
best algorithm count number of set bits in 32-bit integer?

how count number of 1's number have in binary?

so let's have number 45, equal 101101 in binary , has 4 1's in it. what's efficient way write algorithm this?

instead of writing algorithm best use built in function. integer.bitcount()

what makes efficient jvm can treat intrinsic. i.e. recognise , replace whole thing single machine code instruction on platform supports e.g. intel/amd

---

to demonstrate how effective optimisation is

public static void main(string... args) {     perftestintrinsic();      perftestacopy(); }  private static void perftestintrinsic() {     long start = system.nanotime();     long countbits = 0;     (int = 0; < integer.max_value; i++)         countbits += integer.bitcount(i);     long time = system.nanotime() - start;     system.out.printf("intrinsic: each bit count took %.1f ns, countbits=%d%n", (double) time / integer.max_value, countbits); }  private static void perftestacopy() {     long start2 = system.nanotime();     long countbits2 = 0;     (int = 0; < integer.max_value; i++)         countbits2 += mybitcount(i);     long time2 = system.nanotime() - start2;     system.out.printf("copy of same code: each bit count took %.1f ns, countbits=%d%n", (double) time2 / integer.max_value, countbits2); }  // copied integer.bitcount() public static int mybitcount(int i) {     // hd, figure 5-2     = - ((i >>> 1) & 0x55555555);     = (i & 0x33333333) + ((i >>> 2) & 0x33333333);     = (i + (i >>> 4)) & 0x0f0f0f0f;     = + (i >>> 8);     = + (i >>> 16);     return & 0x3f; } 

prints

intrinsic: each bit count took 0.4 ns, countbits=33285996513 copy of same code: each bit count took 2.4 ns, countbits=33285996513 

each bit count using intrinsic version , loop takes 0.4 nano-second on average. using copy of same code takes 6x longer (gets same result)