How to find the position of the first bit set to one? 1

[hyperbug]

I think my last post was confusing because I didn't ask the right question.

I have a 64 bit unsigned integer. I want to find the position of the first (or the last) bit set to 1 without a loop.

I'm using this code:

int position(uint64 number){
for(int i=0; i<64; i++)
if ( (((uint64) 0x01) << i) & number)
return i;
return -1; //All the bits are 0
}

I know that there is a short method to find it using a formula but I have not found it.

 

[Cagliostro]

there is an assembler tst family instructions
you put your integer in eaxand test

_asm mov yourinteger, eax
_asm tst eax, ebx
retrieve number of bit in ebx.
if you use MicrosoftC++ maybe there could be some other instruction than tst Ion Filipski

filipski@excite.com

 

[Zyrenthian]

just out of curiosity, why dont you want to loop? The loop would be the best way to handle this. There is always recursion (if you dont concider that looping )

If you are just looking for the &quot;highest&quot; bit the easy loop is

int shift = 0;

while(value>>shift)
shift++;

return shift;



If you want the lowest bit set to one the %2 works best

int shift = 0;

while( (value>>shift)%2 ==0)
shift++;

return shift


Keep in mind that shift is zero based and not one based.

Matt

 

[lionelhill]

..Ionfilipski, can I make a comment on the assembler approach:
the assembler instruction &quot;test&quot; does an and of the two operands and sets the flags without affecting either operand. As such it's useful for telling you if a particular bit is set (e.g. test ax, 0010000b will tell you if bit 4 is set), but it won't return the position of the set bit. I think the assembler instruction you are thinking of is bscan or something like that - someone else might know). But although it would do the job, it is very, very slow, and might actually not be an improvement on a loop! I haven't timed it. Has anyone out there??

 

[palbano]

>> Has anyone out there??

yeah that was my current assignment LOL

seriously though i am finding this (and the duplicate ) thread interesting... please continue

i still am not 100% sure of the question. locating the &quot;most significant on bit&quot;, yes?



-There are only 10 types of people in the world, those who understand binary and those who don't-

-pete

 

[BoulderBum]

As said before log2x will get you the highest bit

int main()
{
int x;


while ( x != 0 )
{


cout << &quot;Enter number: &quot;;
cin >> x;

cout << &quot;Greatest bit used for &quot; << x << &quot; is bit: &quot;
<< ceil( log( x ) / log( 2 ) + .00000001 ) << '\n' << endl;
// + .00000001 because of computer approximation inaccuracies
}


return 0;
}

 

[lionelhill]

Boulderbum
yes, I was thinking about logs on the way in to work this morning. I like it, it's nice, but remember that the original desire was to find this bit with as little looping as possible. There will undoubtedly be a loop involved in finding log-base-2, and probably more than is strictly necessary since the function will try to return an accurate log, and you only need the integer part. I suspect that the log method will be reliable, simple to understand, but not particularly fast. But again I'm just guessing.

 

[BoulderBum]

I was under the impression that the questioner was looking for a way to find the bit without using loops in his code (even if there are loops in the background). I suspect you're right about the log() functions being slower.

 

[beetee]

No Loops?

a series of tests like this isn't a loop...

(MyInt & 0x80 ? 7 : (MyInt & 0x40 ? 6 : (MyInt & 0x20 : 5))) ...

but it might as well be.

Let's face it, even when you get down to assembly language, it's going to be a loop, or a series of tests like above.

 

[lionelhill]

Yes, I agree, but in the spirit of things it'd be nice to keep the loops down as far as possible. In the other thread about this question someone suggested doing a binary search rather than an ordered search for the bit. Might be a good idea, particularly with very long numbers (questioner is asking for 128 bits, which is quite a lot).
Actually back in the days before processors could guess which way a jump went, it made quite a lot of sense to unroll loops and write out a series of tests as individual instructions.
I'm still plugging look-up tables, because dividing the number of loops by 8 at the cost of 256 bytes of memory strikes me as a good bargain!
Of course there is a lot of educational value in realising that the result is just a rounded log-base-2 and it'd have been a great pity if no one had pointed that out - thanks!

 

[beetee]

or another compromise solution might be to divide the larger bit strings up into 'word-sized' chunks, and test each chunk for zero before checking for bits. I posted a similar solution in the other thread.

And, yes, I agree, whenever possible lookup-tables rule.

But the log technique, while terse, undoubtedly involves a great deal of internal calculation, even with a math co-processor.