Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Нулевые биты в строке.

Автор: Riddik 21.9.2009, 14:28

Нужна функция, возвращающая количество нулевых битов в строке.

Код


int bits(const char *s)
{
    int count=0;
    char temp;
    while(*s)
    {
        temp=*s++;
        for(int i=0; i<8; i++)  
        {
            if(!(temp & 1)) count++;
            temp>>=1;
        }
    }
    return count;
}

Нужна ещё другая реализация - либо более простая, либо более быстрая.
Подскажите, пожалуйста.

Автор: jonie 21.9.2009, 14:43

сделайте предрасчетную матрицу из 256 значений (=sizeof(unsigned char)), в которой будет количество нулевых бит, соотвествующее байту.
Далее итерируйтесь по вашей строке указателем unsigned char* и получайте количество нулевых бит по сбвигу в таблице. Быстро достаточно должно быть.

Автор: Riddik 21.9.2009, 15:11

Спасибо, но вряд ли это будет быстрее - на каждый символ запускать поиск по матрице.
Да и делать эту матрицу...

Есть ещё другие варианты?

Автор: Anikmar 21.9.2009, 15:20

Цитата(Riddik @ 21.9.2009, 15:11

)

Спасибо, но вряд ли это будет быстрее - на каждый символ запускать поиск по матрице.
Да и делать эту матрицу...

Какой поиск?! Там мгновенный доступ по индексу будет без всякого поиска!

Автор: Void 21.9.2009, 15:22

Предвычисленная таблица будет быстрее, притом намного. Быстрее даже чем инструкция POPCNT из SSE4, если применять по одному байту (только что проверил из любопытства).
Если жалко 256 байт, вот коллекция трюков: http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

Автор: Riddik 21.9.2009, 15:39

Понятно, сорри за нубство.

Всем спасибо)