How do I determine which bit is set in an unsigned int64

Question

I have a variable vBit which is an unsigned int64. I know there is exactly one bit set, and I need to figure out which one it is. Currently I do it like this (in Delphi):

vPos := -1;
repeat
  vBit := vBit shr 1;
  inc(vPos);
until vBit = 0;

Is there a faster way? All bit positions are equally likely, so on average the algorithm needs to iterate 32 times. I am looking for an elegant trick with ands and xors and whatnot.

Answer 1

Finding the first bit set is the same as counting the zero bits, so this hack might help. That's a really useful page to bookmark, by the way.

Answer 2

You might do an and with $FFFFFFFF00000000 and if it is non zero add 32 next you and with $FFFF0000FFFF0000 and if non zero, add 16 etc etc. In the end you have your answer and it is very fast:

Result := Ord( ( Val and $FFFFFFFF00000000 ) <> 0 ) * 32 +
          Ord( ( Val and $FFFF0000FFFF0000 ) <> 0 ) * 16 +
          Ord( ( Val and $FF00FF00FF00FF00 ) <> 0 ) * 8 +
          Ord( ( Val and $F0F0F0F0F0F0F0F0 ) <> 0 ) * 4 +
          Ord( ( Val and $CCCCCCCCCCCCCCCC ) <> 0 ) * 2 +
          Ord( ( Val and $AAAAAAAAAAAAAAAA ) <> 0 );

This works only if a single bit is set!

Note: I did not test the routine shown above.