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

← →
Kerk © (2007-10-04 15:47) [0]

Прислали тут тестовое задание.. и есть там вот этот пунктик:

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 15:50) [1]

По-моему, в строчке

> Result := Result + (B and 1);

ты нарисовал полную хню)

> Какой же тогда оптимизированный по скорости?

MBo(c) неоднократно предлагал такой вариант.

← →
Kerk © (2007-10-04 15:52) [2]

Как мне тут верно подсказывают, по скорости - использовать таблицу. :)
А компромиссный какой? :)

← →
shuang (2007-10-04 15:55) [3]

>А компромиссный-то вариант какой?
с постоянной маской и рекурсией

← →
Сергей М. © (2007-10-04 15:55) [4]

> по скорости - использовать таблицу

Емли xlat поможет, тот правильно подсказывают.

> компромиссный какой?

Смотря что подразумевать под "оптимизированный по памяти)..

← →
sniknik © (2007-10-04 15:56) [5]

> Какой же тогда оптимизированный по скорости?
function BitsInByte(B: Byte): Integer;
const
mas: array[0.. ] of integer = (0, 1, ... );
begin
result:= mas[b];
end;

← →
Kerk © (2007-10-04 15:58) [6]

Удалено модератором

← →
Kerk © (2007-10-04 15:59) [7]

> sniknik © (04.10.07 15:56) [5]

Да да.. Я в [2] про это и сказал :)
Осталось компромиссный придумать

← →
Сергей М. © (2007-10-04 16:01) [8]

Удалено модератором

← →
sniknik © (2007-10-04 16:04) [9]

> в) Компромиссный вариант
function BitsInByte(B: Byte): Integer;
begin
result:= byte(b and 1 > 0) + byte(b and 2 > 0) + byte(b and 4 > 0) + ...;
end;

← →
Kerk © (2007-10-04 16:04) [10]

Удалено модератором

← →
Kerk © (2007-10-04 16:05) [11]

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

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

← →
Сергей М. © (2007-10-04 16:06) [12]

Удалено модератором

← →
sniknik © (2007-10-04 16:07) [13]

кстати еще надо будет посмотреть, как бы "компромиссный" не занял меньше памяти чем "оптимальный по памяти"... (слишком мало операций, не займут ли они меньше памяти чем организация цикла... по CPU посмотри)

← →
sniknik © (2007-10-04 16:11) [14]

> А чем он компромиссный?
как чем? работать должен медленнее чем индексная выборка но быстрее чем цикл (они вообще "напряжены", можно кстати цикл while на for заменить он "легче").
и по памяти (размер получающегося кода) должен быть тоже посередине.

← →
Kerk © (2007-10-04 16:19) [15]

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

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

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

← →
Dib@zol © (2007-10-04 16:25) [16]

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;

Ъ?

← →
sniknik © (2007-10-04 16:26) [17]

> Если заменю 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;

← →
sniknik © (2007-10-04 16:36) [18]

[17]
упс... неправильно.

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

← →
homm © (2007-10-04 16:41) [19]

> [18] sniknik © (04.10.07 16:36)

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

← →
Anatoly Podgoretsky © (2007-10-04 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);

← →
Dib@zol © (2007-10-04 16:51) [21]

> [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;

← →
sniknik © (2007-10-04 16:52) [22]

> Вчитайся в [15]
вчитался... и в чем противоречие? все вроде так как и сказал.

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

← →
sniknik © (2007-10-04 16:56) [23]

> Ну если уж пошла такая пьянка, то компромисс это вот что:
ошибка т.к. 0 + 0 + .... + 128 and 128 = 128, а вовсе не 1 как нужно по условию.

← →
oxffff © (2007-10-04 17:01) [24]

> 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 17:03) [25]

> Можно улучшить используя ASM
если улучшиш то это будет не компромиссный а оптимальный вариант. т.что улучшать нельзя... ;)

← →
homm © (2007-10-04 17:18) [26]

> [22] sniknik © (04.10.07 16:52)
> вчитался... и в чем противоречие?

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

← →
clickmaker © (2007-10-04 17:20) [27]

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

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

← →
Kerk © (2007-10-04 17:23) [28]

Спасибо, видимо это все то, что нужно :)
Думаю, асм привлекать не стоит.. все-таки про делфи тест

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

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

На выбор:

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

Еще вариант:

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;

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

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

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

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

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

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

> Или хочешь сказать для вяснения следующей итерации в 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

> [38] sniknik © (04.10.07 23:18)
> берем код

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

> Тем не менее, одна из 8-и итераций займет куда больше времени, нежели одна лишняя инструкция на while.
ну... по поводу слишком малого количества операций я уже высказывал сомнения (не наглядно)... тут спорить глупо.
другое дело если подобный цикл очень длинный или сам по себе используется в другом цикле (ну типа для вычислений суммы "взведенных" битов в массиве из миллионов байт (взяли и применили написанную функцию)). вот тут может сказаться.

Количество бит в байте Найти похожие ветки