Сколько 1-ых битов в байте? :)

← →
Соловьев © (2004-05-27 09:35) [0]

Форумчане, предлагаю конкурс, кто предложит самый оптимальный способ подсчета сабжа. Надо написать функцию на вход которой подается байт, и надо получить на выходе количество 1-ых битов. Это я вчера проходил тест на фирму - "МаксБилл". Надо было использовать С. мой вариант вышел такой, что не налазит ни накакие ворота :)
char cnt_bit(char in) { char result=0, temp=in; while( temp ){ if( 255 == (254|temp) )result++; temp--; } return result; }
Это как из Харькова ехать в Москву через Владивосток. Как оказалось решение очень интересное и самое главное очень простое :)
кто решит? можно и на Паскале. Главное быстродействие. Удачи

← →
Anatoly Podgoretsky © (2004-05-27 09:44) [1]

Критерий оптимальности какой?

← →
Соловьев © (2004-05-27 09:44) [2]

Быстродействие

← →
Ega23 © (2004-05-27 09:45) [3]

1-ых - это "Первых" или "Имеющих значение 1"?

← →
Anatoly Podgoretsky © (2004-05-27 09:47) [4]

Тогда по таблице из 2^SizeOf(Byte) элементов

← →
Соловьев © (2004-05-27 09:47) [5]

> [3] Ega23 © (27.05.04 09:45)

Функция должна выдать - сколько еденичных битов в байте.

← →
Соловьев © (2004-05-27 09:48) [6]

> [4] Anatoly Podgoretsky © (27.05.04 09:47)

подробнее можно?

← →
Danilka © (2004-05-27 09:48) [7]

Дык, вроде было что-то похожее на прошлой неделе в основной, или нет?

[3] Ega23 © (27.05.04 09:45)
Ка я понял, если записать значение в двоичном виде будут нолики и единички. подсчитать скока единичек.

← →
jack128 © (2004-05-27 09:49) [8]

Была тут ветка про красивый код, вот оттуда

[7] Aldor © (18.05.04 21:34)
Из красивого: функция возвращает количество бит в двоичной записи числа

int BitCount(int num)
{
for (int count = 0; num; count++)
num &= num - 1
}

← →
Anatoly Podgoretsky © (2004-05-27 09:49) [9]

Да еще в этом случае и функция не нудна, дополнительное повышение быстродействия, выгдяит так Count := BitsTbl[Byte];

← →
jack128 © (2004-05-27 09:50) [10]

только return count забыли

← →
Соловьев © (2004-05-27 09:50) [11]

> [8] jack128 © (27.05.04 09:49)

нет, это не будет самым быстрым

← →
Соловьев © (2004-05-27 09:51) [12]

> [9] Anatoly Podgoretsky © (27.05.04 09:49)

:)
правильно
А что в таблице?

← →
Anatoly Podgoretsky © (2004-05-27 09:57) [13]

Соловьев © (27.05.04 09:51) [12]
А в таблице прописано количество еддиниц для каждого значения байта, в случае 8 битных байт это числа от 9 до 8. Таблица описывается в виде константного массива

const BitsTbl: array[Byte] of byte = (значения);

← →
Соловьев © (2004-05-27 09:59) [14]

> [13] Anatoly Podgoretsky © (27.05.04 09:57)

Правильно.

← →
Ваххабит (2004-05-27 10:08) [15]

Отряд из восьми ваххабитов = один ваххобайт.

← →
Vlad Oshin © (2004-05-27 10:15) [16]

а 0-1 это сексуальная ориентация членов отряда

← →
MBo © (2004-05-27 10:15) [17]

function Count1Bits(b:byte):byte; asm mov edx,eax and eax,$55 shr edx,1 and edx,$55 add eax,edx mov edx,eax and eax,$33 shr edx,2 and edx,$33 add eax,edx mov edx,eax and eax,$F shr edx,4 and edx,$F add eax,edx end;

← →
MBo © (2004-05-27 10:17) [18]

Паскальный бестабличный аналог :

b:=(b and $55)+((b shr 1) and $55);
b:=(b and $33)+((b shr 2) and $33);
Result:=(b and $F)+((b shr 4) and $F);

← →
WondeRu © (2004-05-27 10:20) [19]

bb1 - твой байт

xor edx,edx
mov al, bb1
mov ecx,8
loop1:
bt al,cl
jnc m1
inc edx
m1:
loop loop1

edx - количество 1-х бит

← →
Соловьев © (2004-05-27 10:20) [20]

> [17] MBo © (27.05.04 10:15)

> [18] MBo © (27.05.04 10:17)

На сколько я знаю - выбать значение из ячейки памяти все-таки быстрее будет, чем суммирование, а насчет асма не знаю, может и самый быстрый способ

← →
jack128 © (2004-05-27 10:28) [21]

> нет, это не будет самым быстрым
но затоо красиво :-)

а самый быстрый уже предложили..

← →
Bless © (2004-05-27 11:46) [22]

MBo ©[18]>

Пусть меня покрасят, если я понял, как это работает! Не объяснишь логику? В смысле, как это в голову пришло, как рассуждал?

← →
Bless © (2004-05-27 11:55) [23]

to Mbo>
Хотел посмотреть твою анкету. Не найдена. Так и было задумано или регистрация пропала?

← →
MBo © (2004-05-27 12:03) [24]

>Соловьев
Да, конечно, табличный способ намного быстрее всех других за счет траты памяти. Приведенный код не имеет особого смысла для байта, но вот его модификация для 32-х или 64-х разрядных чисел совсем неплоха, поскольку имеет алг. сложность O(logN), а не O(N), которая будет, например, у алгоритма типа
for i:=0 to N-1 do begin
if Odd(b) then Inc(ButCount);
b:=b shr 1;
end;

← →
Соловьев © (2004-05-27 12:07) [25]

> [24] MBo © (27.05.04 12:03)

как раз требуется скорость - память не важна

← →
Anatoly Podgoretsky © (2004-05-27 12:16) [26]

Модифицируется обращением к отдельным байтам и суммированием результатов.

← →
Mystic © (2004-05-27 12:20) [27]

Классику надо знать ;)
http://russian.joelonsoftware.com/Articles/Interviewing.html

3. Посчитать все ненулевые биты в байте.

Третья задача показывает, насколько хорошо они учили побитовые операторы в Си... но это уже навык, а не способность, и тут им можно помочь. Интересно посмотреть, как они пишут программу, пересчитывающую все биты в байте, а потом попросить сделать это гораздо, гораздо быстрее. Сообразительный кандидат создаст поисковую таблицу (там ведь всего 256 значений), заполняемую только один раз. С хорошим кандидатом можно даже завести интересную беседу о компромиссах между скоростью выполнения и требуемой памятью. Поднажмите. Скажите, что не хотите тратить время на создание таблицы при инициализации. Очень умные кандидаты могут даже предложить схему кэширования, где биты считаются при первом использовании и сохраняются в таблице, чтобы не пересчитывать их в следующий раз. А самые умные попробуют изобрести способ вычисления значений таблицы, используя для этого некие расширенные методы программирования.

Итого --- не взяли?

← →
MBo © (2004-05-27 12:34) [28]

>Соловьев
Я все понимаю ;)

>Bless © (27.05.04 11:46) [22]
Идея не моя. Числа $55,$33,$F предсталяют собой битовые маски для выделения четных битов, групп по 2 и по 4 бита соответственно
$55=01010101B
$33=00110011B
На первом шаге мы выделяем четные и нечетные биты, второе число сдвигаем и складываем. При этом из числа, например, 00001100B получатся
00000100 и 00000100 (старший бит каждого слагаемого всегда нулевой). Сложив их, получим 00001000B. Следующий шаг требует сдвига на 2, пары битов выделяются, получим 0 и 00000010, и сумма 00000010. Последний шаг для взятого числа (старший ниббл-полубайт нулевой) ничего не изменит, так и останется 00000010B=2

> Итого --- не взяли?

это мне?

Сколько 1-ых битов в байте?

в любом байте первый бит всегда один)

> в любом байте первый бит всегда один)

А если учесть что может быть первый сзади и первый спереди, то два.. :-))

MBo © [28]>

Дык, я ж не о том спросил. Что каждая строчка кода делает, я и сам понимаю. Но каким образом эти действия приводят к желаемому результату, я никак не могу понять.

Для меня не очевидно, что эта последовательность действий для любого байта вернет правильный результат. Но ведь вернет же!

Вот блин, посмотришь такой код, и сразу начинаешь чувствовать нелестную для себя разницу между собой и написавшим его, наводящую на мысль о неправильном выборе профессии. :(

>Bless © (27.05.04 12:58) [32]
На первом шаге мы резервируем четыре счетчика - столько пар бит в байте. В итоге после первой операции в каждой паре бит будет храниться 0, 1, либо 10 (двоичная двойка), что будет означать сумму соседних бит.
На втором шаге получим два счетчика - четверки бит. Каждая четверка будет содержать сумму соседних двух счетчиков (двубитных) предыдущего шага.
Наконец, на третьем шаге, складываем значения двух четырехбитных счетчиков и получаем итоговую сумму бит.

Bless © (27.05.04 12:58) [32]
А ты поиграйся на бумаге с разными значениями, чтобы визуально видеть, что происходит при этом.

Вот еще из занятных трюков (меняет n-й и m-й биты числа)

function BitSwap(i:Integer; n,m:byte):Integer;
begin
if Odd((i shr n) xor (i shr m)) then //биты различны
Result:=i xor ((1 shl m) xor (1 shl m))
else
Result:=i;
end;

>Думкин © (27.05.04 13:23) [38]
Да ладно тебе, код действительно нетривиальный. Самому такое придумать - крыша может поехать ;)
(анонс - в завтрашних задачках будет о едущей крыше ;)))

MBo © (27.05.04 13:31) [39]
> в завтрашних задачках будет о едущей крыше ;)))
У меня еще от бегущей вокруг строя собачки крыша едет :) До сих пор перед сном решаю. Кстати, ее решил кто-то в той ветке или нет (только ответ не говори) ?

Сколько 1-ых битов в байте? :) Найти похожие ветки