|
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
|
|
|
|
|
yep sorry, i fixed it consequently.
thanks
|
|
|
|
|
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
|
|
|
|
|
yes, badKarma already notified me about that point that i did not see firstly
|
|
|
|
|
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
|
|
|
|
|
that's good, but very expensive way though
|
|
|
|
|
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
|
|
|
|
|
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)...
|
|
|
|
|
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 bitset s 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 bitset s - To have the notational convince without space overheads you alluded to above.
Steve
|
|
|
|
|
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 ?
|
|
|
|
|
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
|
|
|
|
|
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
|
|
|
|
|
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;
unsigned int c;
c = BitsSetTable256[v & 0xff] +
BitsSetTable256[(v >> 8) & 0xff] +
BitsSetTable256[(v >> 16) & 0xff] +
BitsSetTable256[v >> 24];
unsigned char * p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] +
BitsSetTable256[p[1]] +
BitsSetTable256[p[2]] +
BitsSetTable256[p[3]];
Cleek | Image Toolkits | Thumbnail maker
|
|
|
|
|
that's what we call hack ?!
[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
[/OT]
|
|
|
|
|
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 ...
People that start writing code immediately are programmers (or hackers), people that ask questions first are Software Engineers - Graham Shanks
|
|
|
|
|
oops, effectively, i missed that point... thanks
|
|
|
|
|
Perfect, would like to give a 7
codito ergo sum
|
|
|
|
|
unsigned int sample;
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;
|
|
|
|
|
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...
|
|
|
|
|
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;
|
|
|
|
|
This works also, and its pretty fast
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
|
|
|
|
|
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...
|
|
|
|
|
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.
|
|
|
|
|
|
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?
|
|
|
|
|