[reqyz]

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

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

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

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

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

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

[Aristarh Dark]

Непонятно зачем это надо, но, если число меньше чем 2^x то его "бинарный размер" = x

[reqyz]

Сообщение от Aristarh Dark

Непонятно зачем это надо, но, если число меньше чем 2^x то его "бинарный размер" = x

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

Код:

  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 значений максимального DWord - овского числа за 3 секунды определяет длину, но это не правильный подход и изврат, помогите с asm

[Freeman]

Ассемблерная команда какая-то была... Забыл.
Посмотрел в справочнике:

Код:

function MostSignificantBit(Value: LongInt): LongInt;
asm
        BSR EAX, EAX
end;

[Bargest]

Посмотрел в справочнике:

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

Код:

function BSR(Value: LongInt): LongInt; assembler;
asm
        BSR EAX, Value
end;

Компилируется это в то же самое BSR eax, eax.
К счастью, эта инструкция переваривает и работу с памятью.

BSR reg32, reg/mem32 - Bit scan reverse on the contents of reg/mem32.

[Freeman]

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

Только такую функцию нельзя использовать с модификатором stdcall

Я написал что написал, а это функция с моделью вызова register. Не надо ля-ля. С использованием мнемнонического имени Value вместо EAX соглашусь. А модификатор assembler давно уже признан устаревшим и не несет никакого смысла.

На плохом форуме кто-то написал быдлокод для Int64. Моя версия будет выглядеть так:

Код:

function MostSignificantBit(Value: Int64): LongInt; overload; // к предыдущей, тоже overload
asm
        BSR EAX, EDX
        JZ @@lo
        SHL EAX, 1
        RET
@@lo:
        BSR EAX, EAX
end;

[icWasya]

Freeman,

Моя версия будет выглядеть так:

Код:

function MostSignificantBit(Value: Int64): LongInt; overload; // к предыдущей, тоже overload
asm
        BSR EAX, EDX
        JZ @@lo
        SHL EAX, 1
        RET
@@lo:
        BSR EAX, EAX
end;

Ну и как ЭТО будет работать?
Value при вызове функции находится в паре регистров, в EDX - старшая часть, в EAX - младшая.
3) BSR EAX, EDX - в EAX грузим номер старшей единицы из старшей половины числа.
4) JZ @@lo - если там ноль, то переходим к строке 8)
5) SHL EAX, 1 - зачам-то умножаем на два, хотя надо прибавить 32

8) BSR EAX, EAX - а теперь в EAX гарантировано ноль

[Freeman]

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

Value при вызове функции находится в паре регистров, в EDX - старшая часть, в EAX - младшая.

Вот именно поэтому и будет работать. Если мы нашли значащий бит в старшей части, младшая нам уже не нужна. А при нулевом значении EDX операция BSR не изменяет EAX, хотя в доке написано, что поведение в этом случае не определено.

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

5) SHL EAX, 1 - зачам-то умножаем на два, хотя надо прибавить 32

А вот за дельное замечение спасибо. Как-то упустил этот момент, а код не отлаживал.

Попутно выяснилось также, что Delphi за каким-то чертом создает стековый кадр в этой простой функции, и голый RET не работает, нужно восстановление EBP. Чтобы не завязываться на причуды Delphi, пришлось добавить второй переход:

Код:

function MostSignificantBit(Value: Int64): LongInt; overload;
asm
        BSR EAX, EDX // неопределенное поведение
        JZ @@lo
        ADD EAX, 32
        JMP @@exit
@@lo:
        BSR EAX, EAX
@@exit:
end;

function MostSignificantBit(Value: Int64): LongInt; overload;
asm
        BSR EDX, EDX  // безопасно во всех смыслах
        JZ @@lo
        MOV EAX, 32
        ADD EAX, EDX
        JMP @@exit
@@lo:
        BSR EAX, EAX
@@exit:
end;

[icWasya]

Попутно выяснилось также, что Delphi за каким-то чертом создает стековый кадр

Вот для этого и пишут assembler

[Bargest]

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

Вот для этого и пишут assembler

Не, новые версии делфы и с assembler создают стековый фрейм (только что проверил). Так что тут Freeman прав.

[M.A.D.M.A.N.]

Извращенцы…
Метод дихотомии не катит?

[Freeman]

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

Не, новые версии делфы и с assembler создают стековый фрейм (только что проверил).

И Delphi 6 тоже.

[M.A.D.M.A.N.]

Кусок кода реализация команды BSR:

Код:

    i := 31;
    while ((j  and $80000000) = 0) do
    begin
      Dec(i);
      j := j shl 1;
    end;

Чо вы какую-то х-ню городите на ассемблере?