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

← →
sniknik © (2007-10-04 23:36) [40]

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

← →
Германн © (2007-10-05 02:11) [41]

<offtop>
Бедный Kerk! Такое количество решений! Да ещё вскорости после сотрясения мозга :-(

← →
oxffff © (2007-10-05 09:18) [42]

> Германн © (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;

← →
Rouse_ © (2007-10-05 09:42) [43]

Мдя, че народ с ассемблером творит? Он же для того и дан чтоб использовать его возможности а не только реализовывать алгоритм :)

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:54) [44]

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

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

← →
Rouse_ © (2007-10-05 09:55) [45]

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

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

← →
oxffff © (2007-10-05 10:03) [46]

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

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

← →
Rouse_ © (2007-10-05 10:20) [47]

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

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

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

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

← →
oxffff © (2007-10-05 10:21) [48]

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

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

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

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

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

← →
oxffff © (2007-10-05 10:25) [49]

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

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

← →
Rouse_ © (2007-10-05 10:28) [50]

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

Чудак, мой алгорит решает задачу в рамках задачи :)
Считает кол-во взведенных бит в байте, а не в Integer. В корайнем случае ничкто не мешает сделать вызов and ax, $FF
А по поводу скорости - замеряй, твой тормозит :)

← →
Rouse_ © (2007-10-05 10:29) [51]

А, инкремент - согласен, тут ступил :)

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

← →
Rouse_ © (2007-10-05 10:30) [52]

блин, теперь точно CLC не нужен :)))

← →
oxffff © (2007-10-05 10:33) [53]

> and ax, $FF

Кто я чудак? Ты что милейший?

LOL.
Твой алгоритм 19 байт работает с byte.

Мой код 17 байт работает c integer и шустрее.

Зритель сделает вывод сам, кому из нас незачет.

← →
oxffff © (2007-10-05 10:36) [54]

> Rouse_ © (05.10.07 10:30) [52]
> блин, теперь точно CLC не нужен :)))

Теперь 18 байт. Но [53].

Ладно. Хватит писками мериться. :)
А то со стороны наверно полный LOL.
Звиняй если чем обидел.

← →
oxffff © (2007-10-05 10:40) [55]

> Rouse_ © (05.10.07 10:29) [51]
> А, инкремент - согласен, тут ступил :)
>
> function BitCount(const Value: Byte): Byte;
> asm
> and ax, $FF
> clc
> shr al, 1
> @@: adc ah, 0
> shr al, 1
> jnz @@
> shr ax, 8
> end;

Вот по размеру хоть идентично. 17 байт.

← →
Rouse_ © (2007-10-05 10:41) [56]

> Мой код 17 байт работает c integer и шустрее.

Ну это то просто проверить :)

function BitCount(const Value: Byte): Byte; asm and ax, $FF shr al, 1 @@: adc ah, 0 shr al, 1 jnz @@ adc ah, 0 shr ax, 8 end; 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 TForm29.FormCreate(Sender: TObject); var I: Integer; V1, V2: DWORD; begin V1 := GetTickCount; for I := 0 to 200000000 do BitCount(123); Memo1.Lines.Add(IntToStr(GetTickCount - V1)); // 5300 - моя победила :) V2 := GetTickCount; for I := 0 to 200000000 do FindBitCount(123); Memo1.Lines.Add(IntToStr(GetTickCount - V2)); //6000 end;

> Звиняй если чем обидел.

Да ты что, какие блин обиды? :) Мыж спорили а не ругались :)

← →
oxffff © (2007-10-05 10:53) [57]

> 5300 - моя победила :)

А вот тут ты лукавишь. Попробуй так

procedure TForm1.FormCreate(Sender: TObject);
var
I: Integer;
V1, V2: DWORD;
begin
V1 := GetTickCount;
for I := 0 to 20000000 do
BitCount(128);
Memo1.Lines.Add(IntToStr(GetTickCount - V1)); // 5300 - моя победила :)
V2 := GetTickCount;
for I := 0 to 20000000 do
FindBitCount(128);
Memo1.Lines.Add(IntToStr(GetTickCount - V2)); //6000
end;

Мой код разгромил твой в 5 раз.

УРА!!!!!!!!!!!!!!!

← →
oxffff © (2007-10-05 11:01) [58]

> Мой код разгромил твой в 5 раз.
>
> УРА!!!!!!!!!!!!!!!

Мой код считает в 5 раз быстрее для четырех байтов, чем твой для одного. Итого в 20 раз byte per byte.

Это разгром!!!! УрА!!!!!!! Четыре раза

← →
Суслик © (2007-10-05 11:03) [59]

на си:

x = (x & 0x55555555) + ((x >> 1) & 0x55555555) x = (x & 0x33333333) + ((x >> 2) & 0x33333333) x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F) x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF) x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF)

для 32-битного числа.

← →
oxffff © (2007-10-05 11:07) [60]

> Суслик © (05.10.07 11:03) [59]

offtop.
Дмитрий я последовал твоему совету. Меня приняли.
Спасибо тебе. :)
Осталось подключить безлимитный инет.

← →
Суслик © (2007-10-05 11:15) [61]

> [59] Суслик © (05.10.07 11:03)

это из книги "Алгоритмические трюки для программистов" Генри Уоррен, мл.
Оригинальное название "Hackers"s Delight" Henry S. Warren, Jr.

Там вся книга из таких вот хитрых решений :)

> [60] oxffff © (05.10.07 11:07)

не офтопь - почта есть.

← →
Rouse_ © (2007-10-05 12:16) [62]

> А вот тут ты лукавишь. Попробуй так

Хе, класс :))) Но 255 рулит по любому :))))

← →
oxffff © (2007-10-05 12:39) [63]

> Rouse_ © (05.10.07 12:16) [62]
>
> > А вот тут ты лукавишь. Попробуй так
>
> Хе, класс :))) Но 255 рулит по любому :))))

Опять лукавиш. У тебя проверяет байт, а меня у 4 байта.
Так что умножай свой результат на четыре. :)

Вот так будет справедливое сравнение .

procedure TForm1.FormCreate(Sender: TObject);
var
I: Integer;
V1, V2: DWORD;
begin
V1 := GetTickCount;
for I := 0 to 200000000 do
begin
BitCount(255);
BitCount(255);
BitCount(255);
BitCount(255);
end;
Memo1.Lines.Add(IntToStr(GetTickCount - V1)); // 5300 - моя победила :)
V2 := GetTickCount;
for I := 0 to 200000000 do
FindBitCount($FFFFFF);
Memo1.Lines.Add(IntToStr(GetTickCount - V2)); //6000
end;

Так что здесь тоже победа за мной.

Тебя может спасти только inline. Да и только ручками.

Но на "неплотных" единичках разрыв будет в разы.

← →
oxffff © (2007-10-05 12:48) [64]

> FindBitCount($FFFFFF);

FindBitCount($FFFFFFFF);

Но тогда ты лидируешь в 2 раза . А inline сделает разрыв больше.

Спешу согласиться, что на плотных единичках твой код будет быстрее
, тогда как мой быстрее будет на неплотных единичках.
Оно и понятно
bsf+shr+inc vs shr+adc

Но на "неплотных" единичках разрыв будет в разы.

← →
oxffff © (2007-10-05 12:49) [65]

> Но на "неплотных" единичках разрыв будет в разы.

А на плотных отставание в разы. :)

← →
Jeer © (2007-10-05 13:00) [66]

oxffff © (05.10.07 11:01) [58]
Rouse_ © (05.10.07 10:41) [56]

Попробуйте Jeer © (04.10.07 18:01) [34] и удивляйтесь.

← →
Суслик © (2007-10-05 13:02) [67]

> [66] Jeer © (05.10.07 13:00)
> oxffff © (05.10.07 11:01) [58]
> Rouse_ © (05.10.07 10:41) [56]
>
> Попробуйте Jeer © (04.10.07 18:01) [34] и удивляйтесь.

а лучше [59]

← →
oxffff © (2007-10-05 13:21) [68]

> Jeer © (05.10.07 13:00) [66]
> oxffff © (05.10.07 11:01) [58]
> Rouse_ © (05.10.07 10:41) [56]
>
> Попробуйте Jeer © (04.10.07 18:01) [34] и удивляйтесь.
>

А чему собственно?

при значении 0

1625 (Rouse)
1344 (oxffff) <-
1734 (Jeer)

при значении 128

7204 (Rouse)
2296 (oxffff) <-
4844 (Jeer)

при значении 31

3953 (Rouse) <-
9609 (oxffff)
4828 (Jeer)

при значении 255

7188 (Rouse)
15812 (oxffff)
5078 (Jeer) <-

а при значении 3242432 ?

может суслик (лень проверять, если честно)

Какие-то неправильные у вас компьютеры:

0:
1172
881
881

128:
6740
1993
1842

31:
4246
7551
1833

255:
6660
11717
1832

> Суслик © (05.10.07 13:40) [69]

> может суслик (лень проверять, если честно)

Раз в 10 суслик быстрее oxffff.
На диапазоне 0..MAXINT

--
Regards, LVT.

> Leonid Troyanovsky © (05.10.07 14:30) [71]
>
> > Суслик © (05.10.07 13:40) [69]
>
> > может суслик (лень проверять, если честно)
>
> Раз в 10 суслик быстрее oxffff.
> На диапазоне 0..MAXINT
>
> --
> Regards, LVT.

Да ладно вам.
На "неплотных" единичках bsf сделает свое дело.
А плотных согласен с вами будет быстрее.

> oxffff © (05.10.07 14:35) [72]

> Давайте пригласим независимых тестеров. :)

Да тут целый форум бездельников - пробуйте, тем более - тяпница.:)

← →
REA (2007-10-05 15:13) [75]

Asm BT еще вроде есть, но это в лоб

на равномерном диапазоне 0..255:
953
2907
453

Jeer всех сделал.

Все эти тесты показывают их непредсказуемость, зависимость от характера данных. Я уже давно, зная эту особенность, не обращаю на них внимания. Всегда можно написать тест, который покажет превосходство.

> [77] Anatoly Podgoretsky © (05.10.07 22:25)

Какой может быть характер у данных при тупом переборе значений от 0 до 255 ???

> на равномерном диапазоне 0..255:

Это как?

> homm © (05.10.07 22:40) [78]

> Какой может быть характер у данных при тупом переборе значений
> от 0 до 255 ???

Характер же зашел дальше, т.е. вплоть до MAXINT.

--
Regards, LVT.

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