Finding number of bits set in a given number

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

BadKarma

This works also, and its pretty fast ;P

  int A = 0xAA000000;
  int B;
  __asm
  {
    mov eax, dword ptr [A] ;
    mov ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    SHL eax,1 ;
    ADC ebx,0 ;
    MOV dword ptr [B],ebx ;
  }

I know the following is better but he said no loops

  int A = 0xAA000000;
  int B;

  __asm
  {
    mov eax, dword ptr [A] ;
    mov ebx,0 ;
    here:
    SHL eax,1 ;
    ADC ebx,0 ;
    CMP eax, 0
    JNE here
    MOV dword ptr [B],ebx ;
  }

codito ergo sum

Stephen Hewitt

The functions are inline - functions which are defined and not just declared in the class definition are implicitly inline. The operators involved compile down to very simple machine code instructions, for example: /32 : sar eax,5 %32 : and eax,0000001Fh For a function which sets or clears a numbered bit there is no avoiding the &=, |= and << operators. As I said the MSVC6 implementation could be better: - The constructors are not efficient. - There is no specialization for the cases when the number of bits can fit into a machine word. If there was we could avoid the [], / and % operations in these cases in the set method. My main point however was to point out that the bitset doesn’t expand the data out to one byte per bit as you suggested. Also with a good implementation of STL and a decent compiler (I haven’t look under the hood of MCVC7’s STL) using a bitset is free (or close to). Steve

BadKarma

If you realy worry about cpu cycles you should write in asm or at least in inline assembly See my post here[^] I agree that in most situation the bitset will prefrom more then adequate. codito ergo sum -- modified at 18:28 Tuesday 7th March, 2006