Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Количество бит установленных в 1? вопрос на собеседовании 
V
    Опции темы
Lamak
  Дата 2.10.2007, 13:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 204
Регистрация: 8.5.2005
Где: Украина,Одесса

Репутация: нет
Всего: 7
Написать функцию которая возвращает кол-во бит установленных в 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

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



--------------------
Роботы - это интересно и увлекательно! 
PM MAIL   Вверх
Fazil6
Дата 2.10.2007, 13:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


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

Репутация: 35
Всего: 60
Код

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


Это сообщение отредактировал(а) Fazil6 - 2.10.2007, 13:52
PM MAIL   Вверх
Lamak
Дата 2.10.2007, 13:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 204
Регистрация: 8.5.2005
Где: Украина,Одесса

Репутация: нет
Всего: 7
Fazil6, скорость твоего алгоритма тоже пропорциональна 32
ты просто избавился от переменной i

Добавлено через 1 минуту и 55 секунд
хотя согласен на некоторых примерах он быстрее
--------------------
Роботы - это интересно и увлекательно! 
PM MAIL   Вверх
Fazil6
Дата 2.10.2007, 13:58 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


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

Репутация: 35
Всего: 60
Цитата(Lamak @  2.10.2007,  13:54 Найти цитируемый пост)
хотя согласен на некоторых примерах он быстрее

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

Добавлено через 7 минут и 17 секунд
http://infolab.stanford.edu/~manku/bitcount/bitcount.html
PM MAIL   Вверх
Lamak
Дата 2.10.2007, 14:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 204
Регистрация: 8.5.2005
Где: Украина,Одесса

Репутация: нет
Всего: 7
Fazil6, +
да я уже понял!
 спасибо за оперативный ответ!

Добавлено через 12 минут и 54 секунды
спасибо за ссылку!
--------------------
Роботы - это интересно и увлекательно! 
PM MAIL   Вверх
xvr
Дата 2.10.2007, 14:24 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223
Цитата(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;
}
PM MAIL   Вверх
Fazil6
Дата 2.10.2007, 14:26 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


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

Репутация: 35
Всего: 60
самый быстрый вариант - использовать предподсчет. Есть в ссылке выше
PM MAIL   Вверх
MAKCim
Дата 2.10.2007, 22:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Воін дZэна
****


Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

Репутация: 52
Всего: 207
Код

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


Это сообщение отредактировал(а) MAKCim - 10.10.2007, 18:06


--------------------
Ах, у елі, ах, у ёлкі, ах, у елі злыя волкі ©
PM MAIL   Вверх
_Michael
Дата 10.10.2007, 17:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: нет
Всего: 6
MAKCim, а можеш немного прокомментировать твой ответ? Как оно работает? smile 

Это сообщение отредактировал(а) _Michael - 10.10.2007, 17:58


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

Саади
PM MAIL   Вверх
MAKCim
Дата 10.10.2007, 18:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Воін дZэна
****


Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

Репутация: 52
Всего: 207
_Michael, 
сдвигаем искомое число на 1 бит вправо
флаг CF принимает значение сдвинутого бита
инструкцией
Код

adcl $0, %0

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


--------------------
Ах, у елі, ах, у ёлкі, ах, у елі злыя волкі ©
PM MAIL   Вверх
_Michael
Дата 10.10.2007, 19:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: нет
Всего: 6
Спасибо, все равно темний лес для меня. Как я понимаю %2 ето типа второй парметр или как?
Но ето уже надо синтаксис смотреть как в сишке асм пользовать


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

Саади
PM MAIL   Вверх
ksili
Дата 15.10.2007, 10:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

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



--------------------
Ничто так не развивает аналитическое мышление, как отладка сложной программы без возможности пошагового выполнения (с)
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0901 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.