Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Количество бит в байте

Страницы: < 1 2 3 4 5 >
Kerk © (2007-10-04 15:47:00)
Прислали тут тестовое задание.. и есть там вот этот пунктик:

3. Напишите функцию, которая принимает на вход байт и возвращает кол-во установленных в нем битов.
Сделайте несколько вариантов функции:
а) Оптимизированной по скорости
б) Оптимизированной по памяти
в) Компромиссный вариант
----

Вижу оптимальным такой вариант:

function BitsInByte(B: Byte): Integer; begin Result := 0; while B > 0 do begin Result := Result + (B and 1); B := B shr 1; end; end;

Это видимо оптимизировано по памяти.. еще меньше памяти использовать невозможно. Какой же тогда оптимизированный по скорости? Ну можно забить массив (1, 2, 4, 8 .... ) и по нему в цикле пробивать and'ом. Это памяти ест чуть больше, но не факт, что работает быстрее моего первого варианта. А компромиссный-то вариант какой? Что-то я запутался. Хелп плиз.

oxffff (2007-10-05 10:25:00) [41]

> Ты по всей видимости считаешь что Carry Flag при входе в
> функцию перманентно очищается? :) LOL :)))

не надо тут LOL.
Ты не понял, у тебя лишний холостой инкремент. Поправь алгоритм.

oxffff (2007-10-05 10:21:00) [42]

> Rouse_ © (05.10.07 09:55) [45]
>
> > А может про bsf почитать?
>
> А может условие задачи прочитать, где говорится про байт?
> :)

Твой алгоритм медленный да еще и бажный. Сделай так

var a:integer;
begin
a:=32434211234342;
showmessage(inttostr(BitCount(a)));

Получи в результате 165

Так что полный Мдя.

Rouse_ (2007-10-05 10:20:00) [43]

> Думаю bsf будет шустрее.

А ты не думай - у тебя компьютер для этого есть, чтоб замерить производительность :)

> Ну и clc для тоже первой итерации тоже Мдя. ;)

Ты по всей видимости считаешь что Carry Flag при входе в функцию перманентно очищается? :) LOL :)))

oxffff (2007-10-05 10:03:00) [44]

> Rouse_ © (05.10.07 09:55) [45]
>
> > А может про bsf почитать?
>
> А может условие задачи прочитать, где говорится про байт?
> :)

Побитовый сдвиг vs bsf и shr.
Думаю bsf будет шустрее.
Ну и clc для тоже первой итерации тоже Мдя. ;)

Rouse_ (2007-10-05 09:55:00) [45]

> А может про bsf почитать?

А может условие задачи прочитать, где говорится про байт? :)

oxffff (2007-10-05 09:54:00) [46]

> Rouse_ © (05.10.07 09:42) [43]
> Мдя, че народ с ассемблером творит? Он же для того и дан
> чтоб использовать его возможности а не только реализовывать
> алгоритм :)

А может про bsf почитать?
Мой пример для 4 байтов, а не для одного. ;)

Rouse_ (2007-10-05 09:42:00) [47]
Мдя, че народ с ассемблером творит? Он же для того и дан чтоб использовать его возможности а не только реализовывать алгоритм :)

function BitCount(const Value: Byte): Byte; asm clc @@: adc ah, 0 shr al, 1 jnz @@ adc ah, 0 shr ax, 8 end;

oxffff (2007-10-05 09:18:00) [48]

> Германн © (05.10.07 02:11) [41]
> <offtop>
> Бедный Kerk! Такое количество решений! Да ещё вскорости
> после сотрясения мозга :-(

function FindBitCount(a:integer):integer;
asm
xor edx,edx;
@Continue:
bsf ecx,eax;
jz @done
inc ecx;
shr eax,cl;
inc edx
jmp @Continue;
@done:
mov eax,edx;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
showmessage(inttostr(FindBitCount(123)));
end;

Германн (2007-10-05 02:11:00) [49]
<offtop>
Бедный Kerk! Такое количество решений! Да ещё вскорости после сотрясения мозга :-(

sniknik (2007-10-04 23:36:00) [50]
> Тем не менее, одна из 8-и итераций займет куда больше времени, нежели одна лишняя инструкция на while.
ну... по поводу слишком малого количества операций я уже высказывал сомнения (не наглядно)... тут спорить глупо.
другое дело если подобный цикл очень длинный или сам по себе используется в другом цикле (ну типа для вычислений суммы "взведенных" битов в массиве из миллионов байт (взяли и применили написанную функцию)). вот тут может сказаться.

homm (2007-10-04 23:20:00) [51]
> [38] sniknik © (04.10.07 23:18)
> берем код

Что-то ты какой-то странный код взял, речь была о конкретном коде :)
Тем не менее, одна из 8-и итераций займет куда больше времени, нежели одна лишняя инструкция на while.

sniknik (2007-10-04 23:18:00) [52]
> Или хочешь сказать для вяснения следующей итерации в for не нужна операция сравнивания?
нужна, но предварительных команд нужно меньше

> Если есть сомнения, можно глянуть в генерируемый код,
берем код
var
i, n: integer;
begin
n:= 0;
for i:= 1 to 100 do
n:= n + Random(10);

Label1.Caption:= IntToStr(n);

n:= 0;
i:= 99;
while i <> 0 do begin
n:= n + Random(10);
i:= i - 1;
end;

Label2.Caption:= IntToStr(n);
end;
глядим
для for выход
dec ebx
jnz -@0f

для while
dec ebx
test ebx, ebx
jnz -@11

homm (2007-10-04 22:26:00) [53]
> [36] tesseract © (04.10.07 22:18)
> А зря - в For вычисление происходит один раз, в while/repeat
> каждую итерацию.

Что? О_о Какие вычисления? Или хочешь сказать для вяснения следующей итерации в for не нужна операция сравнивания? Если есть сомнения, можно глянуть в генерируемый код, в обоих случаях переход держится на ставнении и jnz.

tesseract (2007-10-04 22:18:00) [54]

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

А зря - в For вычисление происходит один раз, в while/repeat каждую итерацию.

homm (2007-10-04 18:06:00) [55]
> [33] sniknik © (04.10.07 17:50)
> прогнать цикл for лишний раз менее "напряжно", чем постоянная
> проверка в while.

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

Jeer (2007-10-04 18:01:00) [56]
Еще вариант:

function CountOne_4(x: byte): byte;
var y: LongWord;
begin
y := x;
y := y * $08040201;
y := y shr 3;
y := y and $11111111;
y := y * $11111111;
Result := y shr 28;
end;

sniknik (2007-10-04 17:50:00) [57]
homm © (04.10.07 17:18) [26]
нет, я про противоречие в моих словах, зачем мне надо было вчитываться в [15]?
чем частный случай с 0 опровергает слова
> смысл в том что прогнать цикл for лишний раз менее "напряжно", чем постоянная проверка в while.
если бы надо было считать "взведенные" биты только в нуле то цикл был бы вообще не нужен, было бы
function BitsInByte(B: Byte): Integer;
begin
Result:= 0;
end;
(также как и значение B, и сама функция)
ну раз это не так, то всетаки
> прогнать цикл for лишний раз менее "напряжно", чем постоянная проверка в while.

Jeer (2007-10-04 17:49:00) [58]
На выбор:

function CountOne(x: byte): byte;
begin
Result := 0;
while (x<>0) do begin
x := (x-1) and x;
Inc(Result);
end;
end;

function CountOne_1(x: byte): byte;
begin
x := x - ((x shr 1) and $55);
x := (x and $33) + (x shr 2) and $33;
end;

function CountOne_2(x: byte): byte;
begin
Result := 0;
while x > 0 do begin
if (x mod 2) = 1 then
Inc (Result);
x := x shr 1;
end;
end;

function CountOne_3(x: byte): byte;
begin
Result := x;
while x <> 0 do begin
x := x shr 1;
Result := Result - x;
end;
end;

homm (2007-10-04 17:30:00) [59]
> [30] Kerk © (04.10.07 17:25)
> В среднем while выполнится 4-5 раз

В среднем цикл выполнится 6,9765625 раз, но для нуля — ноль :)

Kerk (2007-10-04 17:25:00) [60]

> homm © (04.10.07 17:18) [26]

В среднем while выполнится 4-5 раз

Страницы: < 1 2 3 4 5 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »