number of 1's in 32 bit number

Question

I am lookin for a method to have number of 1's in 32 bit number without using a loop in between. can any body help me and provide me the code or algorithm to do so. Thanks in advance.

Balsa

e.g. you want to like from 2344 to 2,3,4,4? please clarify with your input and required output – Interbedded

Answer 1

See Integer.bitCount(int). You can refer to the source code if you want to see how it works; many of the Integer class's bit twiddling routines are taken from Hacker's Delight.

Stereochrome

Yes! Why use an exotic bit hack, when there's a method already available. – Falchion

Using the builtin will also make it easier for future versions of JVM to figure out that the SSE4.2 POPCNT instruction can be used for this. – Headquarters

I was about to post an answer similar to Michael Foukarakis', because that's how I did it before Integer.bitCount() was implemented. Thanks for drawing my attention to the new method. – Pipistrelle

Answer 2

See the canonical reference: Bit Twiddling Hacks

Doersten

Just keep in mind that Java ints are always signed, and modify accordingly. – Stereochrome

Answer 3

Short, obscenely optimized answer (in C):

int pop(unsigned x) {
   x = x - ((x >> 1) & 0x55555555);
   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   x = (x + (x >> 4)) & 0x0F0F0F0F;
   x = x + (x >> 8);
   x = x + (x >> 16);
   return x & 0x0000003F;
}

To see why this magic works, see The Quest for an Accelerated Population Count by Henry S. Warren, Jr. chapter 10 in Beautiful Code.

Scrobiculate

But the question was about Java and in Java there is no unsigned 32-bit int type, and this doesn't work with Java's signed 32-bit int. – Mucky

As far as I can see, Java is not mentioned in the question. And maybe I'm wrong, but tags should not be used for restricting a question to a given language. – Scrobiculate

IMO you're wrong. If a question is tagged Java, what else does that mean, other than that the question is about Java? Maybe the questioner should also mention in the text that they're talking about Java, but if they don't, I don't think it follows that we should pretend it wasn't tagged Java. If you can assume a C answer is acceptable, then I can assume a GCC-only C answer is acceptable and say to use __builtin_popcount. But that doesn't help the questioner much ;-) – Porshaport

For java, there is an unsigned right bit shift (>>>). I think that would give you the correct result. Though perhaps not the result you'd expect. – Charland

Replace the signed shift (">>") with an unsigned shift (">>>"), and this code is exactly what's used in Java's Integer.bitCount(int) method. – Stereochrome

Answer 4

Split the 32 bit number into four 8 bit numbers (see bit shifting operator, casting etc.)

Then use a lookup with 256 entries that converts the 8 bit number into a count of bits set. Add the four results, presto!

Also, see what Mitch Wheat said - bit fiddling can be a lot of fun ;)

Sezen

Answer 5

You can define it recursively:

int bitcount(int x) {
  return (x==0) ? 0 : (x & 1 + bitcount(x/2));
}

The code above is not tested, and probably only works for x>=0. Hopefully, you will get the idea anyways...

Yesterday

-1 for using recursion when "no looping" was requested. Sure, it's not using a loop construct, but it still runs in non-O(1) time. – Fredkin

Sorry. The question resembled a homework problem to me and I wanted to provide a different view. For any performance critical as well as most non-theoretical applications, go for the bit-twiddling solutions! – Yesterday

the classical one is: return (x==0) ? 0 : (1 + bitcount(x & (x - 1))); – Optimist

Answer 6

My personal favourite, directly from Bit Twiddling Hacks:

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

Morelos

NB: This won't work correctly with Java's signed int type -- but the basic idea is the one used by the library. – Stereochrome

I think you want >>> instead of >>. – Pipistrelle

@finnw: I suppose you mean in Java (since no such operator exists in C, where I first saw/used the trick), in that case you're right, maintaining the sign is wrong. – Morelos

@Michael, yes I am assuming Java (the question is tagged as java) – Pipistrelle

Answer 7

Following is JDK 1.5 implementation of of Integer.bitCount

public static int bitCount(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;
}

Twopence