Finding number of bits set in a given number

Amar Sutar

How do I find the number of bits set in a given integer number without using any while/for loop? :confused:

toxcct

myInt mi = /*...*/; //The integer to scan

int iCpt = 0; //The counter of set bits

//For each bits in the integer
for (int i = 0; i < sizeof(mi) * 8; i++) {

//If the most right bit is set
if ((mi & 0x1) == 0x1) {

    //Increasing the counter
    iCpt++;

}

//shifting all bits of 1 position to the right
mi >> 1;

}

printf("mi contains %d '1'\n", iCpt);

ps: don't cross posts the forums. delete your question on the C++/CLI forum, as it is not a managed C++ question -- modified at 6:51 Tuesday 7th March, 2006 (thanks stephen)

Stephen Hewitt

Given this:

#include <iostream>
#include <bitset>
using namespace std;
 
typedef bitset<sizeof(int)*8> IntBitSet;

You can count the bits like this:

cout << IntBitSet(42).count();

Steve

toxcct

that's good, but very expensive way though

Stephen Hewitt

I don't believe this code will work:

v2.0 wrote:

//For each bits in the integer for (int i = 0; i < sizeof(mi); i++) {

Say "MyInt" is of type char. In this case sizeof(char) is 1. So the loop only loops once - But it should loop 8 times. With the following modification it will work:

for (int i = 0; i < sizeof(mi)*8; i++) {

PS: This assumes 8 bit chars - A fair assumption but not universally true on all platforms. Steve

toxcct

yep sorry, i fixed it consequently. thanks

Stephen Hewitt

With templates only the methods actually called are compiled. Also, in general, the methods will be inline. That said the MSVC6 STL bitset class isn't as good as it could be and it will be slower then manually written code. With a good compiler (which MSVC6 is not) and a good STL there is no reason why it can't be just as efficient. Steve

toxcct

because it expands the bits to the array, and as the minimum unit that can be addressed is the byte (not the bit), then it might slower the treatment... i'd recommend using bitarray when it's really needed, for huge bits operations for instance (refering to bjarne stroustrup reflection on the subject)...

Chris Losinger

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive[^]:

const unsigned char BitsSetTable256[] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

unsigned int v; // count the number of bits set in 32-bit value v
unsigned int c; // c is the total bits set in v

// Option 1:
c = BitsSetTable256[v & 0xff] +
BitsSetTable256[(v >> 8) & 0xff] +
BitsSetTable256[(v >> 16) & 0xff] +
BitsSetTable256[v >> 24];

// Option 2:
unsigned char * p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] +
BitsSetTable256[p[1]] +
BitsSetTable256[p[2]] +
BitsSetTable256[p[3]];

Cleek | Image Toolkits | Thumbnail maker

toxcct

:wtf: that's what we call hack ?! :-D [OT] seems that you didn't find back the mail i sent you last week... so here is a summary : it is about your article on SADirRead. i wanted to have your autorization to make some few code refactor, and mostly including some documentation (like Doxygen) on the methods/members, and send you back the zips to update the article... there also was a little bug in the code, but i don't remember which (if you can find back the mail). i'm waiting for your answer... you can email me, i don't have any that aggressive spam filter :-D [/OT]

BadKarma

Perfect, would like to give a 7 :rose: codito ergo sum

Gary R Wheeler

unsigned int sample; // value to count bits in
unsigned int count = ((sample >> 31) & 0x00000001) +
((sample >> 30) & 0x00000001) +
((sample >> 29) & 0x00000001) +
((sample >> 28) & 0x00000001) +
((sample >> 27) & 0x00000001) +
((sample >> 26) & 0x00000001) +
((sample >> 25) & 0x00000001) +
((sample >> 24) & 0x00000001) +
((sample >> 23) & 0x00000001) +
((sample >> 22) & 0x00000001) +
((sample >> 21) & 0x00000001) +
((sample >> 20) & 0x00000001) +
((sample >> 19) & 0x00000001) +
((sample >> 18) & 0x00000001) +
((sample >> 17) & 0x00000001) +
((sample >> 16) & 0x00000001) +
((sample >> 15) & 0x00000001) +
((sample >> 14) & 0x00000001) +
((sample >> 13) & 0x00000001) +
((sample >> 12) & 0x00000001) +
((sample >> 11) & 0x00000001) +
((sample >> 10) & 0x00000001) +
((sample >> 9) & 0x00000001) +
((sample >> 8) & 0x00000001) +
((sample >> 7) & 0x00000001) +
((sample >> 6) & 0x00000001) +
((sample >> 5) & 0x00000001) +
((sample >> 4) & 0x00000001) +
((sample >> 3) & 0x00000001) +
((sample >> 2) & 0x00000001) +
((sample >> 1) & 0x00000001) +
(sample & 0x00000001);

Of course, this assumes that you know that an unsigned int occupies 32 bits.

Software Zen: delete this;

Fold With Us![^]

toxcct

:wtf: is it the "longest/hugest/slowest" contest ? lol

Gary R. Wheeler wrote:

this assumes that you know that an unsigned int occupies 32 bits.

you mean, on a 32 bits systems of course...

Gary R Wheeler

Actually, this is probably a reasonably fast solution, at least on Intel hardware. Bit shifts are done with a barrel shifter, which means all of the >> operations are done only in a 4-10 clock cycles IIRC. The & operations are similar. This means the entire expression could be evaluated in a few hundred clocks. Yes, it's verbose. It has the advantage of simplicity, doesn't require a global table, and could be inlined if necessary.

Software Zen: delete this;

Fold With Us![^]

Stephen Hewitt

v2.0 wrote:

because it expands the bits to the array, and as the minimum unit that can be addressed is the byte

That is not how bitsets work. They store the data as bits and use bit operations ("and" & "or", etc) to address them. It has an embedded class called reference that makes this seamless but it does happen. Here's some code from MSVC6's implementation (I altered the formatting):

bitset<_N>& set(size_t _P, bool _X = true)
{
     if (_N <= _P)
         _Xran();
     if (_X)
         A[_P / _Nb] |= (_Ty)1 << _P % _Nb;
    else
        _A[_P / _Nb] &= ~((_Ty)1 << _P % _Nb);
    return (*this);
}

This is the whole idea behind bitsets - To have the notational convince without space overheads you alluded to above. Steve

toxcct

and don't you think this is comsuming more cpu ? firstly, you call a function, so unless it is inlined, there's all the call stack stuff that comes to work. then each operation is actually a call to an operator function, and in a line like _A[_P / _Nb] &= ~((_Ty)1 << _P % _Nb), you have about 7 operators called !!! do you see what i want to show off ?

Blake Miller

Compared to your original answer, this is a BETTER solution to the problem, because here are the original requirements: How do I find the number of bits set in a given integer number without using any while/for loop I added the emphasis ;) So, if you were a civil engineer and I wanted a brigde, would you construct me a dam or a building instead? The author wanted an answer that did not use a for or while loop. IF that was not the constraint, I would have come up with something like you suggested ... :doh: People that start writing code immediately are programmers (or hackers), people that ask questions first are Software Engineers - Graham Shanks

toxcct

oops, effectively, i missed that point... thanks :)

David Crow

v2.0 wrote:

for (int i = 0; i < sizeof(mi) * 8; i++) {

I believe that amar specifically indicated no while or for loops.

"Let us be thankful for the fools. But for them the rest of us could not succeed." - Mark Twain

"There is no death, only a change of worlds." - Native American Proverb

toxcct

yes, badKarma already notified me about that point that i did not see firstly