Question

Сколько единиц содержится в двоичной записи значения выражения: $4^{2013} + 2^{2012} - 16$?

Accepted Answer

2009

Answer

Идея решения: преобразовать выражение в степени двойки, выполнить арифметику в двоичной системе и подсчитать единицы.

Преобразуем основания к степеням двойки:
- $4^{2013} = (2^2)^{2013} = 2^{4026}$
- $16 = 2^4$

Выражение принимает вид:
$$2^{4026} + 2^{2012} - 2^4$$

В двоичной записи $2^{4026}$ — это единица, за которой следуют 4026 нулей. Добавление $2^{2012}$ даёт число с единицами на позициях 4026 и 2012 (считая от нулевой позиции справа):
$$\underbrace{1\ldots0}_{4026 	ext{ нулей}}\underbrace{1\ldots0}_{2012 	ext{ нулей}}$$

Вычитание $2^4 = 10000_2$ требует заёма из старшего разряда. Единица на позиции 2012 становится нулём, а позиции с 3 по 11 заполняются единицами (заём распространяется через нули). Результат:
$$\underbrace{1\ldots0}_{2013 	ext{ нулей}}\underbrace{1\ldots1}_{2008 	ext{ единиц}}0000_2$$

Итого единиц: $1 + 2008 = 2009$.

Проверка на Python:

```python
s = 4**2013 + 2**2012 - 16
n = bin(s)[2:]
print(n.count('1'))
```

Альтернативное решение на Python:

```python
x = 4**2013 + 2**2012 - 16
s = ''
while x != 0:
    s += str(x % 2)
    x //= 2
s = s[::-1]
print(s.count('1'))
```

![Рисунок](https://ege.sdamgia.ru/formula/svg/fa/fa22581b77a7ea2c58e1a793df552de6.svg)

Задание №14Системы счисления и арифметикаЕГЭ по информатике