# Thread: Am I missing something here? (Calculation issue)

1. ## Am I missing something here? (Calculation issue)

Ok. Let's say I have an integer (X = 0x01000000) and I want to know which bit is active (1-32 or 0-32 depending on how you're counting). There's always only 1 bit active. Is there some equation I could use to do it? The only things I can think of involve looping. I would've thought there's a faster way to reduce it down through shifting or something. I just can't come up with it.

2. Suppose you want to know which bit is active in a character:
Code:
```int main () {
char data = 0x08,
i    = 1;

if ( mask & data ) { /* note bitwise and here. Not logical */
printf( "bit &#37;d (or %d) is 1", i, i-1 ); /* depending on how you count */
}
}

return 0;
}```
Simply apply this to an integer and it should work.

3. I knew I could do it with a loop like that. I was hoping there was a better way with less processing time involved, because this is already being done in a loop that takes a long time.

4. If you're that concerned with time do a binary search...
Code:
```inline int which_bit( char mydata ) {
if ( mydata & 0x0F ) // in upper half
if ( mydata & 0x03 ) // lower quarter
if ( mydata & 0x01 )
return 1;// first bit
else
return 2; // second bit

else // second quarter
if ( mydata & 0x04 )
return 3; // third bit
else
return 4; // fourth bit

else // in lower half
if ( mydata & 0x30 ) // third quarter
if ( mydata & 0x10 )
return 5;// fifth bit
else
return 6; // sixth bit

else // last quarter
if ( mydata & 0x40 )
return 7; // seventh bit
else
return 8; // eighth bit

return 0xFF;
}

int main () {
char data = 0x01;
printf( "Bit #&#37;d", which_bit( data ) );

return 0;
}```
It's up to you to expand it to an int.

5. Why are you so concerned with the time it takes to iterate through this loop? Not to mention that most modern optimizers are fully capable of unrolling the loop in a similar fashion to twomers code. I think the real question that comes to mind when reading this thread is whether twomers name is pronounced like tumors or twom-ers. Random... but that is just how my brain works.

6. I'm bored, so here's a solution (assuming a 4-byte int)
Code:
```inline int which_bit_char( const char mydata ) {
if ( mydata & 0x0F ) // in upper half
if ( mydata & 0x03 ) // lower quarter
if ( mydata & 0x01 )
return 1;// first bit
else
return 2; // second bit

else // second quarter
if ( mydata & 0x04 )
return 3; // third bit
else
return 4; // fourth bit

else // in lower half
if ( mydata & 0x30 )
if ( mydata & 0x10 )
return 5;// fifth bit
else
return 6; // sixth bit

else // second quarter
if ( mydata & 0x40 )
return 7; // seventh bit
else
return 8; // eighth bit

return 0;
}

inline int which_bit_int( int mydata ) {
if ( !mydata )
return 0;

if ( mydata & 0x0000FFFF )
if ( mydata & 0x000000FF )
return which_bit_char( (char)mydata );
else
return 8 + which_bit_char( (char)(mydata>>8) );
else
if ( mydata & 0xFFFF0000 )
if ( mydata & 0x00FF0000 )
return 16 + which_bit_char( (char)(mydata>>16) );
else
return 24 + which_bit_char( (char)(mydata>>24) );
}

int main () {
int mynum = 0x00400;
printf( "Bit #&#37;d", which_bit_int( mynum ) );

return 0;
}```
I'm really bored today. Run this and lemme know what you get
Code:
```#include <stdio.h>
#include <time.h>
int main () {
double bin_time = 0, for_time = 0;

for ( int k=0; k<10; k++ ) {
{
clock_t start, end;
start = clock();

unsigned int num = 0, mask=1, i=1;
for ( unsigned int j=0; j<0xfffffff; j++ )
which_bit_int( num );

end = clock();
bin_time += (double)( end - start ) / (double)CLOCKS_PER_SEC;

printf ( "Binary Search: %f seconds\n",
(double)( end - start ) / (double)CLOCKS_PER_SEC );

}

{
clock_t start, end;
start = clock();

unsigned int num = 0, mask=1, i=1;
for ( unsigned int j=0; j<0xfffffff; j++ )
if ( num & mmask )
break;
end = clock();
for_time += (double)( end - start ) / (double)CLOCKS_PER_SEC;

printf ( "Loop Search: %f seconds\n\n",
(double)( end - start ) / (double)CLOCKS_PER_SEC );
}
}

printf( "total binary time: %f\n", bin_time );
printf( "total loop time: %f\n", for_time );

return 0;
}```
for runs faster for me (mostly, it varies). I've optimisers set to fast.

Edit: I figure the loops must by un-looped, actually. I changed the wrapping for loop to run 1000 times, resulting in 8,321,499,105,000 iterations (maybe. Very back-of-envelope calculation) for both binary and loop searches. My binary search came out in 369.104 seconds and the loop comes out at 368.191... This results in a faster loop-search of about 120fs between per iteration (obviously not really, but with laws of averages 'n' all it is).

A friend did it without optimisers set for 10 wrapping iterations and got 16.81 and 30.17 seconds for binary and for searches respectively.

Conclusion -- Optimisers are smart.

7. If you really need to do this very quickly, then you could use inline assembler, such as:

Code:
```   __asm {
xor   ecx, ecx      // ecx = 0
bsf   eax, data    // First bit from top set into eax
inc   eax
cmovz eax, ecx   // Set to zero if there was no bit set.
}```
If you are using gcc, it needs to be written slightly differently as to syntax, but the method still works.

If you have multiple bits, there are two different instructions, bsf and bsr. bsf starts from the highest bit, bsr starts at the lowest bit.

--
Mats

8. If you do some reading on the mathematical principles of profiling used in optimizers you will find that they truly do aim to please. Which is why I always suggest letting the optimizer work its magic first, then use its generated assembly code as the basis for your own creation. Surely you have seen terminator. We can't beat the machines.... Or can we?

9. I always heard it, but never investigated the effects. Just doin' what the OP said though. The for loop would have prolly sufficed for me.

10. Oh I know. I am just adding in my pedantic narration. It just wouldn't be the same without it, right?

11. matscp: if you really want a fast way why not use Intel's BSF (Bit Scan Forward) or BSR (Bit Scan Reverse) instructions.

12. He did, he used bsf... And mentioned how to use both.

13. Sorry. I didn't see.

14. No biggy. No one is out to humiliate you nor point out your every misstep. Its just how it seems sometimes... Too often, if you ask me.

15. Well, I got to thinking. I'm using an Int64 for this, but not all 64 bits are needed for this specific purpose (the rest are needed for others things though). I came up with an idea for a function with a switch() that might serve my purposes. Checking 20 or so cases shouldn't be bad in terms of time, should it?