How to count the number of 1's a number will have in binary? [duplicate]

Question

Possible Duplicate:
Best algorithm to count the number of set bits in a 32-bit integer?

How do I count the number of 1's a number will have in binary?

So let's say I have the number 45, which is equal to 101101 in binary and has 4 1's in it. What's the most efficient way to write an algorithm to do this?

Answer 1

Instead of writing an algorithm to do this its best to use the built in function. Integer.bitCount()

What makes this especially efficient is that the JVM can treat this as an intrinsic. i.e. recognise and replace the whole thing with a single machine code instruction on a platform which supports it e.g. Intel/AMD

---

To demonstrate how effective this optimisation is

public static void main(String... args) {     perfTestIntrinsic();      perfTestACopy(); }  private static void perfTestIntrinsic() {     long start = System.nanoTime();     long countBits = 0;     for (int i = 0; i < 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;     for (int i = 0; i < 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 from Integer.bitCount() public static int myBitCount(int i) {     // HD, Figure 5-2     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; } 

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 the intrinsic version and loop takes just 0.4 nano-second on average. Using a copy of the same code takes 6x longer (gets the same result)

Answer 2

The most efficient way to count the number of 1's in a 32-bit variable v I know of is:

v = v - ((v >> 1) & 0x55555555); v = (v & 0x33333333) + ((v >> 2) & 0x33333333); c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // c is the result 

Updated: I want to make clear that it's not my code, actually it's older than me. According to Donald Knuth (The Art of Computer Programming Vol IV, p 11), the code first appeared in the first textbook on programming, The Preparation of Programs for an Electronic Digital Computer by Wilkes, Wheeler and Gill (2nd Ed 1957, reprinted 1984). Pages 191–193 of the 2nd edition of the book presented Nifty Parallel Count by D B Gillies and J C P Miller.