Решение задачи №591

Условие задачи №591:

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

Решение

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

Как же сосчитать количество битов во введенном числе? Ведь число же вводится в десятич-ной системе счисления, и его нужно переводить в двоичную?
На самом деле все гораздо проще. Здесь нам поможет одно интересное правило:
Остаток от деления любого десятичного числа x на число p дает нам разряд единиц числа x (его крайний разряд справа) в системе счисления с основанием p.

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

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

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

Теперь, резюмируя вышеприведенный итог, можно поэтапно сформировать сам алгоритм:
1) Вводим число n;
2) Обнуляем счетчик разрядов count. Это делается потому, что значения всех переменных при запуске программы считаются неопределенными, и хотя в большинстве компилято-ров Pascal они обнуляются при запуске, все же считается признаком «хорошего тона» в программировании обнулить значение переменной, которая будет изменяться в процессе работы без предварительного присваивания ей какого-либо значения.
3) Прибавляем к count разряд единиц в двоичной записи числа n, то есть остаток от деле-ния n на 2:

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

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

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