Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > Количество бит установленных в 1?


Автор: Lamak 2.10.2007, 13:40
Написать функцию которая возвращает кол-во бит установленных в 1(например в переменной типа int).
 Я предложил следующее решение: 
Код

int number_of_units(int z)
{
        int counter=0,mask=1;
        for (int i=0;i<32;i++)
        {
                if(z&mask) counter++;
                mask=mask<<1;
        }
        return counter;
}

скорость этого алгоритма пропорциональна 32

Вопрос: Как увеличить скорость алгоритма?
 

Автор: Fazil6 2.10.2007, 13:51
Код

int number_of_units(int z)
{
        int counter=0,mask=1;
        
        while(z)
        {
                if( z&mask ) counter++;
                
                z = z >> 1;
        }
        return counter;
}

Автор: Lamak 2.10.2007, 13:54
Fazil6, скорость твоего алгоритма тоже пропорциональна 32
ты просто избавился от переменной i

Добавлено через 1 минуту и 55 секунд
хотя согласен на некоторых примерах он быстрее

Автор: Fazil6 2.10.2007, 13:58
Цитата(Lamak @  2.10.2007,  13:54 Найти цитируемый пост)
хотя согласен на некоторых примерах он быстрее

такой алгоритм не требует обязательных 32-х итераций

Добавлено через 7 минут и 17 секунд
http://infolab.stanford.edu/~manku/bitcount/bitcount.html

Автор: Lamak 2.10.2007, 14:10
Fazil6, +
да я уже понял!
 спасибо за оперативный ответ!

Добавлено через 12 минут и 54 секунды
спасибо за ссылку!

Автор: xvr 2.10.2007, 14:24
Цитата(Lamak @ 2.10.2007,  13:40)
Написать функцию которая возвращает кол-во бит установленных в 1(например в переменной типа int).
 Я предложил следующее решение: 
Код

int number_of_units(int z)
{
        int counter=0,mask=1;
        for (int i=0;i<32;i++)
        {
                if(z&mask) counter++;
                mask=mask<<1;
        }
        return counter;
}

скорость этого алгоритма пропорциональна 32

Вопрос: Как увеличить скорость алгоритма?

2 варианта:
Код

int number_of_units(int z)
{
 int acc=0;
 while(z)
  {
    ++acc;
    z&=z-1;
  }
 return acc;
}


Второй вариант:
Код

int number_of_units(int z)
{
  z=(z&0x55555555)+((z>> 1)&0x55555555);
  z=(z&0x33333333)+((z>> 2)&0x33333333);
  z=(z&0x0F0F0F0F)+((z>> 4)&0x0F0F0F0F);
  z=(z&0x00FF00FF)+((z>> 8)&0x00FF00FF);
  z=(z&0x0000FFFF)+((z>>16)&0x0000FFFF);
  return z;
}

Автор: Fazil6 2.10.2007, 14:26
самый быстрый вариант - использовать предподсчет. Есть в ссылке выше

Автор: MAKCim 2.10.2007, 22:58
Код

static inline int count(int value) {
    __asm__("1: shrl %2 ; adcl $0, %0 ; decl %1 ; jnz 1b" : "=a" (value) : "r" (32), "r" (value), "0" (0)))
    return value;
}

Автор: _Michael 10.10.2007, 17:58
MAKCim, а можеш немного прокомментировать твой ответ? Как оно работает? smile 

Автор: MAKCim 10.10.2007, 18:11
_Michael, 
сдвигаем искомое число на 1 бит вправо
флаг CF принимает значение сдвинутого бита
инструкцией
Код

adcl $0, %0

увеличиваем (или не изменяем (в зависимости от CF)) общее количество единичных битов
все это в цикле из 32-х итераций

Автор: _Michael 10.10.2007, 19:15
Спасибо, все равно темний лес для меня. Как я понимаю %2 ето типа второй парметр или как?
Но ето уже надо синтаксис смотреть как в сишке асм пользовать

Автор: ksili 15.10.2007, 10:06
В книге Генри Уоррена "Алгоритмические трюки для программистов" вроде есть функция для вычисления этого без всяких ветвлений (то есть нету if, while, else, ну и соответственно jnz). xvr, вроде её и привёл во втором варианте, но возможно там есть и другие варианты

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)