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

You could try taking the base 2 logarithm of the number, but I don't know if that'd be faster. Is this really going to be a performance bottleneck in your system, though?

Answer 2

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 3

Maybe with a hashtree? (not sure it will be faster).

Example in php:

$arr = array();
for($i = 0; $i < 64; $i++)
    $arr[pow($i, 2)] = $i;
// $arr contains { 1:0, 2:1, 4:2, 8:3, 16:4 etc.

$pos = $arr[$x];

Answer 4

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.

Answer 5

You could use the bsf or bsr assembler instruction, which find the first or last bit set in a 32 bit value:

function GetLowestSetBit(AValue: Cardinal): Cardinal; register;
asm
  BSR EAX, EAX
end;

To search in an unsigned 64 bit value you would examine the correct half of it:

procedure TForm1.Button1Click(Sender: TObject);
var
  i: Int64;
  Index: Cardinal;
begin
  i := $8000000000000000;

  if i and $FFFFFFFF <> 0 then
    Index := GetLowestSetBit(i)
  else
    Index := 32 + GetLowestSetBit(i shr 32);
  Caption := IntToStr(Index); // shows 63
end;

Answer 6

If you want to find the most significant bit of UInt64 really fast, you can use the following code:

function SeniorBit(Lo, Hi: LongWord): Integer;
asm
        OR    EDX,EDX
        JZ    @@Lo
        MOV   EAX,EDX
        MOV   EDX,32
@@Lo:
        OR    EAX,EAX
        JZ    @@Done
        BSR   EAX,EAX
        ADD   EAX,EDX
        INC   EAX
@@Done:
end;

The input value is passed in two parts (Lo and Hi longwords). The result is 0 if input is 0, otherwise result is in [1..64]

Answer 7

You could use a strategy like in binary search, instead of checking all bits consecutively. That blows up the code size, but spares some processor cycles.

What actually is not so far away from the Ritsaert Hornstra's answer.

And rewrite this algorithm in assembly, of course.

But is it really worth the pain?