Порахувати кількість одиничних бітів числа

Формулювання. 

Дано натуральне число менше 16. Порахувати кількість його одиничних бітів. Наприклад, якщо дано число 9, запис якого в двійковій системі числення дорівнює 1001(2) (цифра 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: = count + n mod 2;

Строго кажучи, ми могли б не додавати попереднє значення змінної count до залишку від ділення, так як воно все одно було нульовим. Але ми вчинили так для того, щоб зробити код більш однорідним, далі це буде видно. Врахувавши розряд одиниць в двійковому записі n, ми повинні відкинути його, щоб дослідити число далі. Для цього розділимо n на 2. На мові Pascal це буде виглядати так:

n: = n div 2;

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

count: = count + n;

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

program BinaryUnits;
var
n, count: byte;
begin
readln(n);
count := 0;
count := count + n mod 2;
n := n div 2;
count := count + n mod 2;
n := n div 2;
count := count + n mod 2;
n := n div 2;
count := count + n;
writeln(count)
end.