VPF::Нулевые биты в строке. - Форум программистов

Riddik

Дата 21.9.2009, 14:28 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 598
Регистрация: 2.12.2006

Репутация: нет
Всего: нет

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

Код


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;
}

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

Это сообщение отредактировал(а) Riddik - 21.9.2009, 14:29

jonie

Дата 21.9.2009, 14:43 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 5613
Регистрация: 21.8.2005
Где: Владимир

Репутация: 6
Всего: 118

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

--------------------

Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет...

Riddik

Дата 21.9.2009, 15:11 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 598
Регистрация: 2.12.2006

Репутация: нет
Всего: нет

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

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

Anikmar

Дата 21.9.2009, 15:20 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 5
Всего: 59

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

)

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

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

Void

Дата 21.9.2009, 15:22 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 2
Всего: 173

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

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Riddik

Дата 21.9.2009, 15:39 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 598
Регистрация: 2.12.2006

Репутация: нет
Всего: нет

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

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »