Быстро посчитать число ненулевых битов в uint32_t?

Алгоритмические трюки для программистов, глава 5

Bit Twiddling Hacks, есть из чего выбрать, либо «Hacker's delight» как уже подсказали.

__builtin_popcount()

popcount

!!!

Во, оно. Спасибо!

как уже выше упомянули

ну и вообщет по памяти такое :

i=0;while(x){x&=(x-1);i++;}

в делайте есть и по паралельней.

ну а на конкретной железке popcount лучше.

Изучайте Си и одновременно реализуйте свой язык программирования Лисп всего в 1000 строк (комментарий)

как ни странно именно с плюсами(т.е С + класики + шаблончики)

в нижней на данный момент книженции на

http://www.iso-9899.info/wiki/Books Matters Computational pdf

http://www.jjj.de/fxt/fxtbook.pdf

1.8 Counting the bits and blocks of a word 18

ps. на сайте без картинки(кусочка) Рафаэлевой «Афинская школа» на обложке.

pps. походу можно собрать «годную» библиотечку по критерию есть ли «Афинская школа» на обложке по «cs»

Почувствуй класс(Touch of Class: Learning to Programm Well with Objects and Contracts)Бертран Мейер

Разбить на 4 байта и найти в таблице ответ. Или на 2 16бит слова и также в таблице на 65536 значений найти ответ.

for(int i=0; i<32; i++) res += x&(1<<i);

Это не будет работать, кстати.

Разбить на 4 байта и найти в таблице ответ. Или на 2 16бит слова и также в таблице на 65536 значений найти ответ.

Таблицу нужно будет загрузить из памяти в кеш. Не факт, что это будет быстрее, чем посчитать.

ТС, не описывал граничные условия. Может таких расчетов нужно сделать 100500 миллионов.

ТС, не описывал граничные условия. Может таких расчетов нужно сделать 100500 миллионов.

Тогда тут скорее всего дешевле всего будет посчитать каким-то хитрожопым алгоритмом.

Почему?

http://web.itu.edu.tr/kesgin/mul06/intel/instr/bsf.html

оно да, x86 only. И тебе надо проинвертировать.

BSF - Bit Scan Forward (386+)

        Usage:  BSF     dest,src
        Modifies flags: ZF

        Scans source operand for first bit set.  Sets ZF if a bit is found
        set and loads the destination with an index to first set bit.  Clears
        ZF is no bits are found set.  BSF scans forward across bit pattern
        (0-n) while BSR scans in reverse (n-0).

                                 Clocks                 Size
        Operands         808x  286   386   486          Bytes

        reg,reg           -     -   10+3n  6-42           3
        reg,mem           -     -   10+3n  7-43          3-7
        reg32,reg32       -     -   10+3n  6-42          3-7
        reg32,mem32       -     -   10+3n  7-43          3-7

for(int i=0; i<32; i++) res += x&(1<<i);

угу, не будет. Может вот так:

for(int i=0; i<32; i++) res += !!(x&(1<<i));

но лучше двигать сам x

как-то так

res = 0;
if(x&(1<<31)) return res;
x <<= 1;
x |= 1;
res++;
while((x&(1<<31))==0)
{
   res++;
   x<<=1;
   if(!x)   break;
}
return res;

for(int i=0; i<32; i++) res += !!(x&(1<<i));

for(int i=0; i<32; i++) res += (x&(1<<i));

И чем они отличаются?

И чем они отличаются?

тем, что второе прибавляет 1,2,4,8,16…

А первое 1,1,1,1,1,1…

Я так делаю:

unsigned long long pgt_popcount(unsigned long long _value)
{
#ifdef __GNUC__
	return __builtin_popcount(_value);
#else /* __GNUC__ */
	unsigned long long ret = 0;
	for (unsigned long long i = 0; i < sizeof(unsigned long long) * CHAR_BIT; i++)
		if ((_value >> i) & 1ULL)
			ret++;
	return ret;
#endif /* __GNUC__ */
}

в выше упомянутой ссылке (Быстро посчитать число ненулевых битов в uint32_t? (комментарий))

«was first published by Peter Wegner in CACM 3 (1960), 322. :

для святой ibm704

LXA ZERO,2    IR2 counts number of ones and is initializedto zero
LXA NBITS,1   NBITS containsthe number of bitsin a machine word
LDQ WORD      Load word whose ones are to be countedinto the MQ
TQP *+2       Test MQ Plus
TXI *+I,2,1   Count ones in IR2
RQL 1         Rotate MQ left
TIX *-3,1,1 Index and trransfer ifIRI > 1

There isan alternateand oftenfastermethod of counting ones where the number of instructionsexecuted depends not on the number of bitsin a machine word, but directly on the number of ones in the word tested.The method depends on the fact that ifone is subtractedfrom the least significanthitof a positivebinary number N and the logical AND operationisperformed on the numbers N and N- 1,then the resulting number has one less one in it, the least significant one having been eliminated.

в первоначальном с мельким багом по сути идёт копирование исходного слова побитово :)

Да, спасибо, ступил.

! и ~ относятся друг к другу также как && и &

В книге Генри Уоррена - «Алгоритмические трюки для программистов» есть несколько глав посвященным подобным операциям. С примерами на сях.

тем, что второе прибавляет 1,2,4,8,16…

Это каким образом двойное ! делает такую последовательность?

Чему будет равно значение val в примере ниже?
bool b = true;
bool val = !!b;

! и ~ относятся друг к другу также как && и &

Быстро посчитать число ненулевых битов в uint32_t? (комментарий)

! всякое не ноль делает нулём , ноль же 1

!! всякое не ноль делает 1, ноль же ноль

операция ! определена на целых («унаследовано» ещё из С)

последовательность не даёт(там лингвистически чел не точен и это простительно ) там всякий единичный бит вычленяется и получается некоторое не_ноль, из которого затем получают 1.

твой же пример с bool там всего «2 значения» в котором !! есть идентичность.

Ага, я понял.

Потому что x&(1<<i) даёт разный результат в зависимости от положения проверяемого бита. Например, 0b1111&(1<<2) = 0b100. Чтобы получить строго единицу, правильно было бы написать (x>>i)&1.

А, ну да, точно. Спасибо :)

Просто очень близкая конструкция вида if (x & (1<<i)) cnt++ - будет работать, а вот cnt += (x & (1<<i)) - уже нет.

int NumberOfSetBits(int i)
{
     i = i - ((i >> 1) & 0x55555555);
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
     return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

хакир 32битноинтный?

кошерны только 32-х битные инты, всё остальное харам

еретик

Это каким образом двойное ! делает такую последовательность?

никаким, речь про _второе_

ещё раз:

for(int i=0; i<32; i++) res += (x&(1<<i));

Быстро посчитать число ненулевых битов в uint32_t? (комментарий)