|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vladislav Irdullin 2:5093/55.111 16 Jul 2001 22:57:34
To : Ђ¤аҐ© Њ ЄбЁ¬ҐЄ®
Subject : найти ближайшую бОльшую степень двойки минус 1
--------------------------------------------------------------------------------
АМ> Число - целое 8 байт (Int64)
АМ> необх найти ближайшую бОльшую степень двойки минус 1, т.е.
АМ> для 4...7 - это 7;
АМ> для 32...63 - это 63;
АМ> Делаю так:
АМ> i := i or (i shr 1);
АМ> i := i or (i shr 2);
АМ> i := i or (i shr 4);
АМ> i := i or (i shr 8);
АМ> i := i or (i shr 16);
АМ> i := i or (i shr 32);
АМ> Второй вариант короче, но в 6 раз медленнее:
АМ> i := 2 shl Floor(log2(i))-1 // Floor - целая часть числа
АМ> Есть ли более оптимальный вариант? Hичего в голову не приходит.
я дам саму логику для 32-битных чисел на дельфи/ассемблере, в общем сам принцип
чтоб ты понял, я в комментариях всё описал.
Number - начальное число, возвращает ближайшую бОльшую степень двойки минус 1
LongWord - это беззнаковый 32-битный тип данных в дельфи.
type
UINT32 = LongWord;
function HазовиСам(Number: UINT32): UINT32; register;
label
L1;
asm
xor ecx,ecx // обнуляем ecx, если этого не сделать, то в случае
// Number = 0 после следующей команды в ecx останется
// случайное число
bsr ecx,eax // получаем в ecx номер первого бита слева, равного
// единице
// (Number в соглашении о вызовах "register" передаётся в
// регистре eax)
inc ecx // увеличиваем номер бита, чтоб получить степень двойки
xor eax,eax // eax = 0
inc eax // eax = 1
shl eax,cl // получаем в eax ближайшую бОльшую степень двойки
dec eax // уменьшаем на единицу, результат по этому же соглашению
// должен возвращаться в eax
jnz L1 // если eax <> 0, то выходим
dec eax // в противном случае у нас получилось переполнение, т.е.
// ввели число в диапазоне $80000000..$ffffffff, т.е.
// младшие 5 бит регистра cl были равны нулю при сдвиге
// и eax не поменялось после сдвига, после первого
// dec eax регистр eax стал =0, так что нужно его
// уменьшить ещё разок
L1: ret
end;
для 64-битных чисел два двойных слова передаются через стек. Сделай сам.
WBR, Влад | РФ, г. Hабережные Челны
... army| "л" стоит где-то в конце алфавита. пусть она будет 8-й
--- бабы, ребятня, мужики..
* Origin: (.ъ silence ъ.) (2:5093/55.111)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
