Мастера 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'ом. Это памяти ест чуть больше, но не факт, что работает быстрее моего первого варианта. А компромиссный-то вариант какой? Что-то я запутался. Хелп плиз.

Германн (2007-10-04 17:25:00) [61]

> clickmaker © (04.10.07 17:20) [27]

Ну и что? В военное время количество может быть и не равным 8!!

Kerk (2007-10-04 17:23:00) [62]
Спасибо, видимо это все то, что нужно :)
Думаю, асм привлекать не стоит.. все-таки про делфи тест

clickmaker (2007-10-04 17:20:00) [63]

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

блин, нельзя же так пугать...

homm (2007-10-04 17:18:00) [64]
> [22] sniknik © (04.10.07 16:52)
> вчитался... и в чем противоречие?

Цикл While работает «пока», а цикл for работает от и до. Колическво шагов, приводящих к резкльтату в цикле for всегда равно 8-и, в while число шаков зависит от исходных данных, и для нуля, равно нулю.

sniknik (2007-10-04 17:03:00) [65]
> Можно улучшить используя ASM
если улучшиш то это будет не компромиссный а оптимальный вариант. т.что улучшать нельзя... ;)

oxffff (2007-10-04 17:01:00) [66]

> Anatoly Podgoretsky © (04.10.07 16:44) [20]
> > sniknik (04.10.2007 16:26:17) [17]
>
> Компромисом будет
>
>
> Result:= Result + byte(B and 1 > 0);
> Result:= Result + byte(B and 2 > 0);
> Result:= Result + byte(B and 4 > 0);
> Result:= Result + byte(B and 8 > 0);
> Result:= Result + byte(B and 16 > 0);
> Result:= Result + byte(B and 32 > 0);
> Result:= Result + byte(B and 64 > 0);
> Result:= Result + byte(B and 128 > 0);

Можно улучшить используя ASM

BSF—Bit Scan Forward

sniknik (2007-10-04 16:56:00) [67]
> Ну если уж пошла такая пьянка, то компромисс это вот что:
ошибка т.к. 0 + 0 + .... + 128 and 128 = 128, а вовсе не 1 как нужно по условию.

sniknik (2007-10-04 16:52:00) [68]
> Вчитайся в [15]
вчитался... и в чем противоречие? все вроде так как и сказал.

> Компромисом будет
ага. см. [9].

Dib@zol (2007-10-04 16:51:00) [69]
> [20] Anatoly Podgoretsky © (04.10.07 16:44)

Ну если уж пошла такая пьянка, то компромисс это вот что:

Result:= Result + B and 1 + B and 2 + B and 4 + B and 8 + B and 16 + B and 32 + B and 64 + B and 128;

Anatoly Podgoretsky (2007-10-04 16:44:00) [70]
> sniknik (04.10.2007 16:26:17) [17]

Компромисом будет

Result:= Result + byte(B and 1 > 0); Result:= Result + byte(B and 2 > 0); Result:= Result + byte(B and 4 > 0); Result:= Result + byte(B and 8 > 0); Result:= Result + byte(B and 16 > 0); Result:= Result + byte(B and 32 > 0); Result:= Result + byte(B and 64 > 0); Result:= Result + byte(B and 128 > 0);

homm (2007-10-04 16:41:00) [71]
> [18] sniknik © (04.10.07 16:36)

Вчитайся в [15]

sniknik (2007-10-04 16:36:00) [72]
[17]
упс... неправильно.

ну, неважно, ты понял. смысл в том что прогнать цикл for лишний раз менее "напряжно", чем постоянная проверка в while.

sniknik (2007-10-04 16:26:00) [73]
> Если заменю while на for
ну не просто же так, логику тоже подправить...

function BitsInByte(B: Byte): Integer;
var i: byte;
begin
Result := 0;
for i:= 1 to 8 do
Result:= Result + byte(B and i > 0);
end;

Dib@zol (2007-10-04 16:25:00) [74]
function BitsOn(B:BYTE):BYTE;
asm
XOR BH, BH;
@1:
MOV BL, B;
SHR B, 1;
AND BL, 1;
ADD BH, BL;
CMP B, 0;
JNZ @1;
MOV Result, BH;
end;

Ъ?

Kerk (2007-10-04 16:19:00) [75]

> sniknik © (04.10.07 16:11) [14]

Если заменю while на for, то цикл гарантированно выполнится 8 раз..а while выполнится от 0 до 8 раз

Пойду в CPU смотреть :)

sniknik (2007-10-04 16:11:00) [76]
> А чем он компромиссный?
как чем? работать должен медленнее чем индексная выборка но быстрее чем цикл (они вообще "напряжены", можно кстати цикл while на for заменить он "легче").
и по памяти (размер получающегося кода) должен быть тоже посередине.

sniknik (2007-10-04 16:07:00) [77]
кстати еще надо будет посмотреть, как бы "компромиссный" не занял меньше памяти чем "оптимальный по памяти"... (слишком мало операций, не займут ли они меньше памяти чем организация цикла... по CPU посмотри)

Сергей М. (2007-10-04 16:06:00) [78]
Удалено модератором

Kerk (2007-10-04 16:05:00) [79]

> sniknik © (04.10.07 16:04) [9]

А чем он компромиссный?

Kerk (2007-10-04 16:04:00) [80]
Удалено модератором

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

Наверх

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