Сколько единиц

Данная задачка судя по всему типовая в ЕГЭ по информатике, алгоритм ее решения в общем случае следующий: перевести число в двоичную форму (например, тут — http://floatingpoint.ru/online/dec2bin.php) и подсчитать количество единиц — калькулятор нулей и единиц в двоичной записи числа

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

Для этого нужно помнить несколько первых степеней двойки и двоичные записи по крайней мере некоторых чисел от 1 до 15:

1024 = 2^10, 512 = 2^9, 256 = 2^8, 128 = 2^7, 64 = 2^6, 32 = 2^5, 16 = 2^4

15 = 1111, 14 = 1110, 13 = 1101, 12 = 1100, 11 = 1011, 10 = 1010, 9 = 1001, 8 = 1000, 7 = 111, 6 = 110, 5 = 101, 4 = 100, 3 = 11, 2 = 10, 1 = 1.

Так же могут оказаться полезны некоторые суммы, например:

192 = 128 + 64

160 = 128 + 32

320 = 256 + 64

640 = 512 + 128

Приведем некоторые типовые примеры.

Сколько единиц в двоичной записи числа 1025?

1025 = 1024 + 1  1024 = 2^10 это степень двойки, а единица так и будет единицей, следовательно, 
всего в двоичной записи числа 1025 ровно 2 единицы.

10000000001

Сколько единиц в двоичной записи числа 519?

519 = 512 + 7  512 = 2^9 это степень двойки, а 7 записывается в двоичной системе как 111 и содержит три единицы, 
следовательно, всего в двоичной записи числа 519 содержится ровно 4 единицы.

1000000111

Сколько единиц в двоичной записи числа 514?

514 = 512 + 2  Слагаемые 512 = 2^9 и 2 = 2^1 - это степени двойки, следовательно, в двоичной записи числа 514 
ровно 2 единицы.

1000000010

Сколько единиц в двоичной записи числа 127?

127 = 128 - 1  Число 128 представляет собой целую степень двойки и равняется 2^7, требуя таким образом 
для своей записи ровно 8 бит: 10000000  10000000-1 = 1111111  Следовательно, в записи числа 127 содержится 7 единиц.

1111111

Сколько единиц в двоичной записи числа 195?

195 = 192 + 3 = 128 + 64 + 3  128 = 2^7  64 = 2^6  3 = 11 в двоичной системе и содержит 2 единицы. Таким образом в двоичной записи числа 195 
содержится 4 единицы.

11000011

Сколько единиц в двоичной записи числа 173?

173 = 160 + 13  160 = 128 + 32 = 2^7 + 2^5, а 13 = 1101 в двоичной системе.   Тогда всего получим 5 единиц.

10101101

Сколько единиц в двоичной записи числа 3458?

3458 = 2048 + 1410  1410 = 1024 + 386  386 = 256 + 130  130 = 128 + 2  Таким образом 3458 = 2^11 + 2^10 + 2^8 + 2^7 + 2^1 и всего будет 5 единиц.

110110000010

floatingpoint.ru

Решение №1

Для того, чтобы узнать, сколько единиц в двоичной записи числа 12F0₁₆, необходимо выполнить несколько действий. Перевести из 16-чной системы счисления в двоичную напрямую сложно. Поэтому:

Сначала переведём это число в десятичную систему счисления (путём умножения).
Затем переведём получившийся результат в двоичную систему счисления.

Шаг 1. Переводим в десятичную систему счисления

(12F0_{16}=0times 16^0+Ftimes 16^1 + 2times 16^2 + 1times16^3 =\ = 0 + 15times16 + 2times 256 + 256times 16 = 0+240+512+4096=4848)

Как быстрее работать со степенями 16-ти?

Гораздо удобнее выучить таблицу степеней двойки (см. в конце) и переводить всё в степени двойки, в этом случае подсчёт делается существенно быстрее:

(0times 16^0+Ftimes 16^1 + 2times 16^2 + 1times 16^3=\ = 0 + 240 + 2times 2^{4^2}+2^{4^3}=\ = 0 + 240 + 2times 2^8 + 2^{12}=\ = 0 + 240 + 2^9 + 2^{12} = \ = 0 + 240 + 512 + 4096 = 4848)

Шаг 2. Переводим из десятичной системы счисления в двоичную

4848 = 1001011110000₂

Шаг 3. Считаем количество единиц

Посчитали, получили 6 единиц. Итого, исходное число 12F0₁₆ в двоичной записи имеет 6 единиц.

Таблица степеней двойки

(2^1 = 2 \ 2^2 = 4 \ 2^3 = 8 \ 2^4 = 16 \ 2^5 = 32 \ 2^6 = 64 \ 2^7 = 128 \ 2^8 = 256 \ 2^9 = 512 \ 2^10 = 1024 \ 2^11 = 2048 \ 2^12 = 4096)

newtonew.com