Finding number of bits set in a given number

[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