LINUX.ORG.RU

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


0

0

Здравствуйте. Необходимо максимально быстро и технично подсчитать число двоичных "1" в байте на Си. Можно было использовать побитовые сдвиги для этого...но может есть более рациональный способ? Может кто поделится мыслями? А если это сделать используя asm'овские вставки?

> #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

klalafuda ★☆☆
()

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

dn2010 ★★★★★
()
Ответ на: комментарий от dn2010

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

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

// wbr

klalafuda ★☆☆
()

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

redgremlin ★★★★★
()

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

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

tailgunner ★★★★★
()

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

Miguel ★★★★★
()


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

// wbr

klalafuda ★☆☆
()
Ответ на: комментарий от tailgunner

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

dn2010 ★★★★★
()

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;

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

wfrr ★★☆
()
Ответ на: комментарий от wfrr

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

не самый.

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

klalafuda ★☆☆
()

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

anterior
() автор топика

Написано на 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

anonymous
()
Ответ на: комментарий от dn2010

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

Legioner ★★★★★
()
Ответ на: комментарий от klalafuda

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

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

Deleted
()
Ответ на: комментарий от klalafuda

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

dilmah ★★★★★
()

Из книги ``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;
}

trapezoid
()
Ответ на: комментарий от wfrr

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

tailgunner ★★★★★
()
Ответ на: комментарий от anonymous

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

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

tailgunner ★★★★★
()
Ответ на: комментарий от tailgunner

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

anonymous
()
Ответ на: комментарий от anonymous

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

dilmah ★★★★★
()
Ответ на: комментарий от dilmah

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

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

Pavval ★★★★★
()

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

ugoday ★★★★★
()
Ответ на: комментарий от ugoday

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

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

tailgunner ★★★★★
()
Ответ на: комментарий от tailgunner

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

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

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

dilmah ★★★★★
()
Ответ на: комментарий от trapezoid

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

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

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

true_admin ★★★★★
()
Ответ на: комментарий от true_admin

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

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

koTuk
()
Ответ на: комментарий от koTuk

Ну, табличку для 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раз быстрее оказался :)

true_admin ★★★★★
()
Ответ на: комментарий от Assaron

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

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

Assaron
()
Ответ на: комментарий от tailgunner

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

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

anonymous
()

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

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

Assaron
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.