C / C++ / MFC Discussion Boards

Re: Finding number of bits set in a given number

toxcct7-Mar-06 3:12

7-Mar-06 3:12

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 ?

Re: Finding number of bits set in a given number

Stephen Hewitt7-Mar-06 11:53

Stephen Hewitt

7-Mar-06 11:53

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

Re: Finding number of bits set in a given number

BadKarma7-Mar-06 12:17

BadKarma

7-Mar-06 12:17

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

Re: Finding number of bits set in a given number

C^hris L^osinger7-Mar-06 2:07

C^hris L^osinger

7-Mar-06 2:07

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

Re: Finding number of bits set in a given number

toxcct7-Mar-06 2:25

toxcct

7-Mar-06 2:25

that's what we call hack ?! Big Grin | :-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 Big Grin | :-D

[/OT]

Re: Finding number of bits set in a given number

Blake Miller7-Mar-06 3:23

Blake Miller

7-Mar-06 3:23

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 Wink | ;)

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 ... D'Oh! | :doh:

People that start writing code immediately are programmers (or hackers), people that ask questions first are Software Engineers - Graham Shanks

Re: Finding number of bits set in a given number

toxcct7-Mar-06 3:27

toxcct

7-Mar-06 3:27

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

Re: Finding number of bits set in a given number

BadKarma7-Mar-06 2:30

BadKarma

7-Mar-06 2:30

Perfect, would like to give a 7 Rose | [Rose]

codito ergo sum

Re: Finding number of bits set in a given number

Gary R. Wheeler7-Mar-06 2:51

Gary R. Wheeler

7-Mar-06 2:51

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![^]

Re: Finding number of bits set in a given number

toxcct7-Mar-06 2:53

toxcct

7-Mar-06 2:53

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...

Re: Finding number of bits set in a given number

Gary R. Wheeler7-Mar-06 2:59

Gary R. Wheeler

7-Mar-06 2:59

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![^]

Re: Finding number of bits set in a given number

BadKarma7-Mar-06 6:03

BadKarma

7-Mar-06 6:03

This works also, and its pretty fast Poke tongue | ;-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

DirectShow SDK download

Storm-blade7-Mar-06 0:03

Storm-blade

7-Mar-06 0:03

Hi,
Does anyone know where I can download the Latest DirectShow SDK?
It seems Microsoft is trying to discourage people from using directshow by hiding the SDK. its been removed from the DirectX SDK, and I can't find a download link for it with either Google or MSDN searches...

I need to render video to a Direct3D9 texture, the samples for doing this were in the directshow section of the directX SDK, which has been removed.

Thanks...

Re: DirectShow SDK download

Justin Tay7-Mar-06 5:26

Justin Tay

7-Mar-06 5:26

DirectShow has been moved into the Platform SDK but all the project files have been stripped out. I think the best one to get is the DirectX SDK February 2005 Extras.

Re: question

toxcct7-Mar-06 0:01

toxcct

7-Mar-06 0:01

::ShellExecute(NULL, "open", "the_file_to_open_htm", NULL, NULL, SW_SHOWNORMAL);[^]

Using VC7.1 compiler under VC6 IDE.... woes.... :S

kevingpo6-Mar-06 23:52

kevingpo

6-Mar-06 23:52

Has anyone tried compiling a VC6 MFC application using the VC7.1 compiler?

I followed this simple article on making VC6 to use the VC7.1 compiler.
http://pixwiki.bafsoft.com/wiki/index.php/Using_the_Optimizing_VC7_Compiler_with_the_VC6_IDE

Then all the errors I've been getting have been from the actual C:\Program
Files\Microsoft Visual Studio\VC98\MFC\Include\ folder (loads of template
syntax errors).

Surely Microsoft must've made a portability/conversion for VC6 MFC to be
used under VC7.1?

Re: Using VC7.1 compiler under VC6 IDE.... woes.... :S

toxcct6-Mar-06 23:59

toxcct

6-Mar-06 23:59

the VC6 compiler wasn't standard compliant...

so it is totally normal to get errors when migrating VC6 projects to VC7.1...

even if the errors come from the compiler's include\ folder, the problem comes from your code...

Re: Using VC7.1 compiler under VC6 IDE.... woes.... :S

kevingpo7-Mar-06 0:03

kevingpo

7-Mar-06 0:03

But it was saying specific things about MFC source files... eg. missing ;, type not found. It's probably namespaces, and maybe a little syntax change. I do not know the inner workings of MFC nor the difference between the VC6 & VC7.1 template syntax.

Currently am looking for a nice script/conversion tool to convert VC6 source files into VC7.1 compliant.

What happened to MFC/ATL in VS.NET2003? Does MFC/ATL still exist in VS.NET2003 or have they been replaced with STL?

Re: Using VC7.1 compiler under VC6 IDE.... woes.... :S

mkuhac7-Mar-06 2:01

mkuhac

7-Mar-06 2:01

kevingpo wrote:
Does MFC/ATL still exist in VS.NET2003 or have they been replaced with STL?

This is illogical question because STL is collection oriented, while MFC and/or ATL/WTL are GUI oriented. Can you build Windows application with just collections (no menus, windows, buttons...)??

Re: Using VC7.1 compiler under VC6 IDE.... woes.... :S

Gary R. Wheeler7-Mar-06 2:55

Gary R. Wheeler

7-Mar-06 2:55

It sounds like you are trying to use the 7.1 compiler and the VC6 MFC headers. You would be better off to use the 7.1 headers. Check the include file paths in your 7.1 settings, and make sure the 7.1 include paths come first.

Software Zen: delete this;

Fold With Us![^]

List View Multiple Selection

Anil_vvs6-Mar-06 23:39

Anil_vvs

6-Mar-06 23:39