Подсчёт количества единичных битов в числе может использоваться, например, для контроля передаваемой информации в качестве расширения кодового расстояния.
Для решения этой задачи могут использоваться различные варианты.
Традиционный метод
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
using namespace std;
int getOnes(unsigned int number)
{
unsigned int mask = 1;
int count = 0;
for (int i = 0; i < 32; i++)
{
if ((number & mask) > 0)
count++;
mask = mask << 1;
}
return count;
}
int main()
{
unsigned int number;
system("chcp 1251");
system("cls");
cout << "N: ";
cin >> number;
int cnt = getOnes(number);
cout << "Количество единиц во введенном числе: " << cnt << endl;
cin.get();
cin.get();
return 0;
}
Метод Кёрнигана
{\displaystyle n\ \& \ (n-1)}
обнуляет в числе последнюю единицу.{\displaystyle\begin{array}{r} \& \begin{array}{r} 10000011\\ 10000010\\ \end{array} \\ \hline \begin{array}{r} 10000010 \end{array} \end{array}}
{\displaystyle\begin{array}{r} \& \begin{array}{r} 10000100\\ 10000011\\ \end{array} \\ \hline \begin{array}{r} 10000000 \end{array} \end{array}}
2
3
4
5
6
7
8
9
10
{
int count = 0;
while (number > 0)
{
number = number & (number — 1);
count++;
}
return count;
}
Табличный метод
Табличный метод предполагает первоначальное заполнение массива количества единиц в числе для некоторого диапазона чисел (например, для байта). Затем, зная число в заданном диапазоне, подставляется значение из массива.
Такой способ требует больше емкостных ресурсов на хранение массива количества единиц, а также временных ресурсов на заполнение исходного массива значений, однако сам подсчёт количества единиц в числе осуществляется быстрее.
Для заполнения исходного массива количества единиц можно воспользоваться свойством
{\displaystyle {Ones(N) = \begin{cases} Ones(N/2) & N \ — \ even\\ 1 + Ones(N/2) & N \ — \ odd\\\end{cases}}}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
using namespace std;
int ones[256] = { 0 };
void initOnesTable()
{
for (int i = 0; i < 256; i++)
ones = (i & 1) + ones;
}
int getOnesTable(unsigned int number)
{
return ones[number & 0xFF] + ones[(number >> 8) & 0xFF] +
ones[(number >> 16) & 0xFF] + ones[(number >> 24) & 0xFF];
}
int main()
{
unsigned int number;
system("chcp 1251");
system("cls");
initOnesTable();
cout << "N: ";
cin >> number;
int cnt = getOnesTable(number);
cout << "Количество единиц во введенном числе: " << cnt << endl;
cin.get();
cin.get();
return 0;
}