Функция, которая подсчитывает количество единиц в двоичной записи числа - C (СИ)
Формулировка задачи:
В книге Кернигана и Ритчи представлена данная функция, которая подсчитывает количество единиц в двоичной записи числа:
Я не понимаю, зачем записывать единицу в восьмеричной системе счисления:
Что изменится, если я запишу единицу, например, в десятичной системе:
#include <stdio.h>
/* bitcount: подсчитывает единицы в двоичной записи x */
int bitcount(unsigned x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01)
b++;
return b;
}
int main()
{
unsigned x;
scanf("%u", &x);
printf("%d\n", bitcount(x));
return 0;
}if (x & 01)
if (x & 1)
Решение задачи: «Функция, которая подсчитывает количество единиц в двоичной записи числа»
textual
Листинг программы
unsigned int rez = 0; unsigned char c; .................................... c = (c & 85) + ((c>>1) & 85); c = (c & 51) + ((c>>2) & 51); c = (c & 15) + (c>>4); rez = c;
Объяснение кода листинга программы
Код реализует алгоритм подсчёта количества единиц в двоичной записи числа. Вот список действий:
- Инициализировать переменную rez единицей.
- В каждой итерации алгоритма:
- Считать очередную цифру числа (в двоичной системе счисления) в переменную c.
- Вычислить значение c после сдвига на 1 разряд вправо и наложения маски 85 на старший бит.
- Вычислить значение c после сдвига на 2 разряда вправо и наложения маски 51 на старший бит.
- Вычислить значение c после сдвига на 4 разряда вправо и наложения маски 15 на старший бит.
- Прибавить к переменной rez значение c.
- Вернуть значение rez.