Форум программистов, компьютерный форум CyberForum.ru

Подсчёт нулей в двоичном коде - C++

Восстановить пароль Регистрация
 
bloodvlad
0 / 0 / 0
Регистрация: 23.10.2014
Сообщений: 57
25.11.2014, 23:41     Подсчёт нулей в двоичном коде #1
Есть код который возвращает количество единиц в двоичном представлении целого числа,
как переделать что бы он считал количество нулей ?
C
1
2
3
4
5
6
7
8
9
10
int count (int a)
{
int r=0;
while(a)
{
a&=(a-1);
++r;
}
return r;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
RefSol
220 / 159 / 39
Регистрация: 31.10.2010
Сообщений: 496
26.11.2014, 01:02     Подсчёт нулей в двоичном коде #2
bloodvlad, очень просто: отнять от общей длинны двоичного представления числа число единиц:
C++
1
2
3
4
5
6
7
8
int count (int a) {
  int r=0;
  while(a) {
    a&=(a-1);
    ++r;
  }
  return (8*sizeof(int) - r);
}
или так:

C++
1
2
3
4
5
6
7
8
int count (int a) {
  int r=8*sizeof(int);
  while(a) {
    a&=(a-1);
    --r;
  }
  return (r);
}
OnePiece
33 / 33 / 22
Регистрация: 22.02.2014
Сообщений: 107
26.11.2014, 01:16     Подсчёт нулей в двоичном коде #3
Я думаю, что запись 2 чисел подразумевается не в виде 32 знаков.
А столько, сколько достаточно, то есть 2^n>a.
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2899 / 1435 / 395
Регистрация: 18.10.2014
Сообщений: 2,643
26.11.2014, 01:21     Подсчёт нулей в двоичном коде #4
Цитата Сообщение от RefSol Посмотреть сообщение
8*sizeof(int) - r
Эта константа называется 'CHAR_BIT'. Не 8, а 'CHAR_BIT'.
OnePiece
33 / 33 / 22
Регистрация: 22.02.2014
Сообщений: 107
26.11.2014, 01:23     Подсчёт нулей в двоичном коде #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
int count (int a)
{
int r=0;
while(pow(2,r)<=a)
    r++;
while(a)
{
a&=(a-1);
r--;
}
return r;
}
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
2899 / 1435 / 395
Регистрация: 18.10.2014
Сообщений: 2,643
26.11.2014, 01:58     Подсчёт нулей в двоичном коде #6
Это не так эффективно, как вариант с вычитанием, но все же

C++
1
2
3
4
5
6
7
8
9
unsigned count(unsigned a)
{
  unsigned r = 0;
 
  for (; a != 0; a >>= 1)
    r  += (~a & 1);
 
  return r;
}
Добавлено через 34 минуты
Можно еще предложить вариант, основанный на том же принципе, что и оригинальный код

C++
1
2
3
4
5
6
7
8
9
10
11
unsigned count(unsigned a)
{
  unsigned r = 0;
 
  for (unsigned bit = ~a & ~(~a - 1);
       bit < a;
       a |= bit, bit = ~a & ~(~a - 1))
    ++r;
 
  return r;
}
Выражение '~a & ~(~a - 1)' можно заменить на '~(a | (~a - 1))'
Yandex
Объявления
26.11.2014, 01:58     Подсчёт нулей в двоичном коде
Ответ Создать тему
Опции темы

Текущее время: 17:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru