Посчитать количество единичных битов числа

Формулировка. Дано натуральное число меньше 16. Посчитать количество его единичных битов. Например, если дано число 9, запись которого в двоичной системе счисления равна 10012 (подстрочная цифра 2 справа от числа означает, что оно записано в двоичной системе счисления), то количество его единичных битов равно 2.

Решение. Нам необходима переменная для ввода с клавиатуры. Обозначим ее как n. Так как мы должны накапливать количество найденных битов, то возникает потребность в еще одной переменной. Обозначим ее как count («count» в переводе с англ. означает «считать», «подсчет» и т. д.). Переменные возьмем типа byte (они могут принимать значения от 0 до 255), и пусть в данном случае такой объем избыточен, но это не принципиально важно.

Как же сосчитать количество битов во введенном числе? Ведь число же вводится в десятичной системе счисления, и его нужно переводить в двоичную?

На самом деле все гораздо проще. Здесь нам поможет одно интересное правило:

Остаток от деления любого числа x в системе счисления с основанием p на само число p дает нам разряд единиц числа x (его крайний разряд справа).

То есть, в десятичной системе счисления мы получаем разряд единиц некоторого числа, взяв остаток от деления этого числа на 10. Возьмем, например, число 3468. Если остаток от деления на 10 равен 8, то есть разряду единиц этого числа.

Такие же правила господствуют и в арифметике в других системах счисления, и в том числе в двоичной системе. Предлагаю поэкспериментировать: запишите на бумаге десятичное число, затем, используя любой калькулятор с функцией перевода из одной системы счисления в другую, переведите это число в двоичную систему счисления и также запишите результат. Затем разделите исходное число на 2 и снова переведите в двоичную систему. Как оно изменилось в результате? Вполне очевидно, что у него пропал крайний разряд справа, или, как мы уже говорили ранее, разряд единиц.

Но как это использовать для решения задачи? Воспользуемся тем, что в двоичной записи числа нет цифр, кроме 0 и 1. Легко убедиться в том, что сложив все разряды двоичного числа, мы получаем как раз таки количество его единичных битов. Это значит, что вместо проверки значений разрядов двоичного представления числа мы можем прибавлять к счетчику сами эти разряды – если в разряде был 0, значение счетчика не изменится, а если 1, то повысится на единицу.

Теперь, резюмируя вышеприведенный итог, можно поэтапно сформировать сам алгоритм:

1)      Вводим число n;

2)      Обнуляем счетчик разрядов count. Это делается потому, что значения всех переменных при запуске программы считаются неопределенными, и хотя в большинстве компиляторов Pascal они обнуляются при запуске, все же считается признаком «хорошего тона» в программировании обнулить значение переменной, которая будет изменяться в процессе работы без предварительного присваивания ей какого-либо значения.

3)      Прибавляем к count разряд единиц в двоичной записи числа n, то есть остаток от деления n на 2:

count := count + n mod 2;

Строго говоря, мы могли бы не прибавлять предыдущее значение переменной count к остатку от деления, так как оно все равно было нулевым. Но мы поступили так для того, чтобы сделать код более однородным, далее это будет видно. Учтя разряд единиц в двоичной записи n, мы должны отбросить его, чтобы исследовать число далее. Для этого разделим n на 2. На языке Pascal это будет выглядеть так:

n := n div 2;

4)      Теперь нам нужно еще два раза повторить п. 3 , после чего останется единственный двоичный разряд числа n, который можно просто прибавить к счетчику без каких-либо дополнений:

count := count + n;

5)      В результате в переменной count будет храниться количество единичных разрядов в двоичной записи исходного числа. Осталось лишь вывести ее на экран.

Код:

  1. program BinaryUnits;
  2. var
  3. n, count: byte;
  4. begin
  5. readln(n);
  6. count := 0;
  7. count := count + n mod 2;
  8. n := n div 2;
  9. count := count + n mod 2;
  10. n := n div 2;
  11. count := count + n mod 2;
  12. n := n div 2;
  13. count := count + n;
  14. writeln(count)
  15. end.

Программа работает правильно на всех вариантах правильных исходных данных, в чем несложно убедиться с помощью простой проверки.