Вопросы Теги

Как я определяю, какой бит установлен в неподписанном int64

У меня есть переменная vBit, который является неподписанным int64. Я знаю, что существует точно один набор битов, и я должен выяснить, какой это. В настоящее время я делаю это как это (в Delphi):

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

Существует ли более быстрый путь? Все позиции двоичного разряда одинаково вероятны, таким образом, в среднем алгоритм должен выполнить итерации 32 раза. Я ищу изящный прием с ands и xors и этажеркой.

5
задан Svein Bringsli 8 January 2010 в 11:28
поделиться

7 ответов

Поиск первого набора битов совпадает с подсчетом нулевых битов, поэтому этот взлом может помочь . Это, кстати, очень полезная страница для закладки.

8
ответ дан 18 December 2019 в 11:57
поделиться

Вы можете сделать и с $FFFFFFF00000000 и если это не нулевое добавление 32. Далее вы и с $FFF0000FFFF0000 и если не ноль, добавьте 16 и т.д. и т.п. В конце концов, у вас есть ответ, и он очень быстрый:

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 );

Это работает только в том случае, если установлен один бит!

Примечание: Я не тестировал рутину, показанную выше.

.
3
ответ дан 18 December 2019 в 11:57
поделиться

Можно попробовать взять базовый логарифм числа 2, но я не знаю, будет ли это быстрее. Неужели это действительно будет узким местом в вашей системе?

1
ответ дан 18 December 2019 в 11:57
поделиться

Может, с хэштри? (не уверен, что это будет быстрее).

Пример на 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];
1
ответ дан 18 December 2019 в 11:57
поделиться

Можно воспользоваться командой ассемблера bsf или bsr, которые находят первый или последний бит, установленный в 32-битном значении:

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

Для поиска в 64-битном беззнаковом значении вы бы рассмотрели правильную его половину:

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;
0
ответ дан 18 December 2019 в 11:57
поделиться

Если вы хотите очень быстро найти самый старший бит UInt64, вы можете использовать следующий код: 

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;

Входное значение передается в двух частях (длинные слова Lo и Hi). Результат равен 0, если вход равен 0, иначе результат будет в [1..64]

.
2
ответ дан 18 December 2019 в 11:57
поделиться

Можно использовать стратегию, как в бинарном поиске, вместо того, чтобы проверять все биты подряд. Это увеличивает размер кода, но избавляет от некоторых процессорных циклов.

Что на самом деле не так далеко от Рицаэрта Хорнстра. Ответ.

И, конечно, перепишите этот алгоритм в сборке.

Но действительно ли это стоит боли?

0
ответ дан 18 December 2019 в 11:57
поделиться
Другие вопросы по тегам:

Похожие вопросы: