Как подсчитать количество «1» в байте?

> #include <inttypes.h>
> #include <stdio.h>
> #include <stdlib.h>
> #include <time.h>
> #include <unistd.h>
>
> typedef uint16_t entry_t;
>
> #define HASH_SIZE       (1 << (sizeof(entry_t) * 8))
> #define HASH_MASK       (HASH_SIZE - 1)
> #define ARRAY_SIZE      10000
>
> static unsigned char hash[HASH_SIZE];
> static entry_t array[ARRAY_SIZE];
>
> int
> main(int argc, char *argv[])
> {
>     const unsigned char bits[16] = {
>         0, 1, 1, 2,
>         1, 2, 2, 3,
>         1, 2, 2, 3,
>         2, 3, 3, 4 };
>     unsigned long nbits;
>     unsigned int val, i;
>
>     /* Setup bits hash table */
>     for (i = 0; i < HASH_SIZE; i++) {
>         val = i;
>         hash[i] = 0;
>         while (val) {
>             hash[i] += bits[val & 0xF];
>             val >>= 4;
>         }
>     }
>
>     printf("Hash table is %d entries %d bytes maks 0x%X\n",
>         HASH_SIZE, HASH_SIZE * sizeof(hash[0]), HASH_MASK);
>
>     /* Init pseudo-random number generator */
>     srand(getpid() ^ time(0));
>
>     /* Fill in source data array with random values */
>     for (i = 0; i < ARRAY_SIZE; i++) {
>         array[i] = rand();
>     }
>
>     /* Calc number of set bits in the source data array */
>     nbits = 0;
>     for (i = 0; i < ARRAY_SIZE; i++) {
>         nbits += hash[array[i] & HASH_MASK];
>     }
>
>     printf("Number of bits %lu\n", nbits);
>
>     return EXIT_SUCCESS;
> }

// wbr

восемь раз сдвигаешь на бит, побитово & с единичкой, складываешь то, что получилось.

> восемь раз сдвигаешь на бит, побитово & с единичкой, складываешь то, что получилось.

это долго. в том смысле, что можно сделать заметно быстрее. тем более для 8ми битного байта.

// wbr

ЕМНИП, в асме для этого команда есть. Но последний раз на нем я 7 лет назад кодин по книжке, может и подводить.

> Можно было использовать побитовые сдвиги для этого...но может есть более рациональный способ?

табличный, как написал klalafuda. только таблицу можно сделать на 256 значений.

Массив на 256 элементов сделай уже, да?

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

// wbr

А может кому-нибудь не будет лень проверить? Меня терзают смутные сомнения, что на x86 битовые операции и сложение выполнятся быстрее, чем вычисление адреса нужного элемента массива.

char i;

int bitCount = i&0x01 + (i&0x02)?1:0 + (i&0x04)?1:0 + (i&0x08)?1:0 + (i&0x10)?1:0 + (i&0x20)?1:0 + (i&0x40)?1:0 + (i&0x80)?1:0;

самый быдлокодерский вариант

> самый быдлокодерский вариант

не самый.

int
calc_bit_count(uint8_t val)
{
    if (val == 0) {
        return 0;
    } else if (val == 1) {
        return 1;
    } else if (val == 2) {
        return 1;
    } else if (val == 3) {
        return 2;
    } else if (val == 4) {
        return 1;
    .........
    } else {
        return 8;
    }
}

// wbr

всем спасибо за идею насчёт таблицы, как я и сам про неё не догадался даже не знаю...)

Написано на tcl, но в C можно перевести один в один.

proc bits x {
    set x [expr ($x&85)+(($x>>1)&85)]
    set x [expr ($x&51)+(($x>>2)&51)]
    set x [expr ($x&15)+(($x>>4)&15)]
    return $x
}

// rystsov-denis

А чего его вычислять? Одно сложение. А 16 элементов массива в любой кеш поместятся.

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

ты пытался к ним устроится? :)

> ты пытался к ним устроится? :)

скорее, они пытались меня устроить к себе. но ничего у них не вышло.

// wbr

меня про биты не спрашивали. Спрашивали про итератор std::map, задачки про роботов на планете и вариацию ханойских башен.

Из книги ``Beautiful Code'' (O'Reilly):

int pop(uint32_t x)
{
  x = x - ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x + (x >> 4)) & 0x0F0F0F0F;
  x = x + (x >> 8);
  x = x + (x >> 16);
  return x & 0x0000003F;
}

Что это за подрасстрельный ужоснах?

Это какято слишком умная хрень
http://community.livejournal.com/ru_algorithms/40235.html?thread=294699#t294699

вот еще http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

а все равно получается выборка из таблицы быстрее работает ... хотя казалосьбы, посчитать десяток операций в процессоре быстрее чем в память лезть ...

> вот еще http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

Этот ужоснах еще и медленный. Исторический курьез, короче.

> хотя казалосьбы, посчитать десяток операций в процессоре быстрее чем в память лезть ...

За командами тоже нужно лезть в память. Все эти прикольные трюки имели смысл, когда хранить 256-байт таблицу в памяти было слишком дорого.

дык за командами в любом случае лезть ... за теми которые из таблицы выбирают тоже ...

> дык за командами в любом случае лезть ... за теми которые из таблицы выбирают тоже ...

Там команд явно меньше.

ну и что что меньше ... там поди они пачками как-нить загружаются ... типа получить 10 командр из памяти столько же времени сколько 20 и 30 ...

> ну и что что меньше ...

То, что они и загружаются быстрее, и выполняются.

странно это все вот ...

таблица на 256 байт вся в кэше. Меня гораздо больше удивило, что по ссылке выше выходит что использование таблицы на 65536 элементов еще быстрее.

>Меня гораздо больше удивило, что по ссылке выше выходит что использование таблицы на 65536 элементов еще быстрее.

Кеш большой.... А бенчмарк небось только это и гоняет. Потому из кеша массив даже и не вылазит.

странно, что до сих пор никто не предложил привести число к стоковому виду и сосчитать количество вхождений символа "1" в нём.

> странно, что до сих пор никто не предложил привести число к стоковому виду и сосчитать количество вхождений символа "1" в нём.

Как это "никто"? Вот ты предложил...

> > > странно, что до сих пор никто не предложил

> Как это "никто"? Вот ты предложил...

он предложил с тех пор, а не до сих пор

> Из книги ``Beautiful Code'' (O'Reilly):

Чорт, я посмотрел на это и почувствовал себя тупым. Без "бумажки" точно не въеду...

Так какой способ лучше? Котируется ли в гугле способ с побитовым сдвигом или это тока я один так программирую?

>Так какой способ лучше?

Сколько раз надо повторить что табличный метод будет самым быстрым ? Какой для тебя лучше - тебе решать :)

Ну, табличку для uint64 не сделаешь :). Хотя, можно uint64 разбить на байты.

Прогнал бенчмарки, короче, примитивный сдвиговый способ очень быстро работает, делая миллионы
 вычислений на моём пеньке. Стоит ли городить огород с этими всеми таблицами?

У меня вот такой код выполнился за 18 секунд(собирался так: gcc -std=gnu99):

    for (uint32_t x=0; x<100000000; x++) {
        for (i=0,bits=0,value=6666; i<BIT_CNT; i++,bits+=value&1,value=value>>1) {
        sum+=value;
        }
    }

Если собрать с оптимизацией то ещё быстрее будет. Правда,
табличный способ всё равно в 60раз быстрее оказался :)

std::cin >> x;
int n = 0;
while (x > 0)
{
  ++n;
  x = x & (x - 1); 
}
std::cout << n << endl;

считает количество единичных бит в х

работает за О(ответ)

красиво

Это была классика. Вот то же самое, но понятнее:

#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x) ((x) - (((x)>>1)&0x77777777) \
- (((x)>>2)&0x33333333) \
- (((x)>>3)&0x11111111))

а, кстати, по поводу массива - это интересно

если памяти жалко, то можно заполнить массив для 4х битных чисел, и разбивать байт на 2 куска и сладывать, что-то типа: return a[x && 15]+a[x >> 4]; (если х - байт)