бинарная длина целого числа

[Biohazard]

Доброго времени суток уважаемые форумчане.

есть число X, как мы знаем в памяти оно хранится как набор единиц и нулей например 13 это 1101 и т д

задача: узнать положение ближайшей единицы, то-есть, четвертая с конца, значит бинарный размер = 4

предполагаю что делается на asm, благо в делфи его можно прикручивать.

пытался сделать через trunc(log2(abs(x))+1), работало, но использование функций, работающих с ieee745 или как его там, к сожалению запрещено,

подскажите, как можно найти позицию единички?
заранее благодарю

[waleri]

подсчитайте сколько раз можно поделить на 2 без остатка.

[Biohazard]

Сообщение от waleri

подсчитайте сколько раз можно поделить на 2 без остатка.

это конечно гениально и я бы никогда не додумался, но работает это медленно и подход не верный. реализация уже есть, но для чисел, типа in64 достаточно больших работает медленно, да и использовать деление, когда я уверен что можно просто как то прочесть память, не совсем правильный подход. была бы задача столь тривиальной, я бы не спрашивал, в asm-е кто нибудь тут разбирается?

[Serge_Bliznykov]

Biohazard, как это может долго работать?!!

var k : integer;
  N : int64;
begin
  N :=  787789000098000;
  k := 0;
  while N>0 do begin
    inc(k);
    N := N shr 1
  end;
  ShowMessage('бинарная длина числа = '+IntToStr(k))
end;

думаю, что подобный код на современном процессоре может подсчитает более пяти миллионов чисел за секунду... Вам нужно быстрее?

[waleri]

Сообщение от Biohazard

была бы задача столь тривиальной, я бы не спрашивал, в asm-е кто нибудь тут разбирается?

Ну тогда нате: http://graphics.stanford.edu/~seander/bithacks.html
Там есть и алгоритм перевертывания данных + алгоритм поиска наиболее старшего бита.

[Biohazard]

Сообщение от Serge_Bliznykov

Biohazard, как это может долго работать?!!

var k : integer;
  N : int64;
begin
  N :=  787789000098000;
  k := 0;
  while N>0 do begin
    inc(k);
    N := N shr 1
  end;
  ShowMessage('бинарная длина числа = '+IntToStr(k))
end;

думаю, что подобный код на современном процессоре может подсчитает более пяти миллионов чисел за секунду... Вам нужно быстрее?

  function GetCount(const Base:byte;X:Int64):cardinal;//для любой системы измерения
  var
    z:int64;
    zp:cardinal;
    Base3:cardinal;
    xx:int64;
  begin
    Result:=0;
    Base3:=Base*Base*base;//увеличиваем скорость
    xx:=0;
    while X>0 do
    begin
      z:=1;
      zp:=0;
      while X>=Z do
      begin
        Z:=Z*base3;
        xx:=X;
        X:=X div Z;
        inc(zp,3);
        inc(Result,zp);
      end;
    end;
    if(xx<>0)and(X=0)then//исправляем потери
    begin
      Z:=Z div (Base*Base);
      xx:=xx div Z;
      if(xx=0)then
        dec(Result,2)
      else
      if(xx<base)then
        dec(Result,1);
    end;
  end;

с этого и начинал, немножко ускорил 10 000 000 за 3 секунды, но к сожалению недостаточно, встроенный в делфи логарифм2 справляется быстрее на больших числах "9223372036854775807"

[f.hump]

__asm {

BSR rax, [N]
INC rax
MOV [k], rax

}

[Biohazard]

Сообщение от f.hump

__asm {

BSR rax, [N]
INC rax
MOV [k], rax

}

Спасибо, в асме я не силён, компилятор делфей ругается, может что то не так применяю?

function rax(N:int64):byte;
asm
  BSR rax, [N]
  INC rax
  MOV [k], rax
end;

можете пояснить?

[f.hump]

то что я написал, оно для х64

для 32х бит (если N 64-х битное) можно как-то так


LEA edx, [N]

CMP DWORD PTR [edx+4], 0
JZ nohigh
BSR eax, [edx+4]
ADD eax, 33
JMP done
nohigh:

BSR eax, [edx]
INC eax

done:
; MOV [k], eax

[Biohazard]

эх, на первую строку ругается, говорит [Error] Unit1.pas(38): Invalid register combination ну и т д, ладно, всё равно спасибо, попытаюсь дальще сам додуматься)