Question

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

Accepted Answer

2013

Answer

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

Преобразуем выражение, используя $4 = 2^2$:

$$4^{2014} + 2^{2015} - 8 = 2^{4028} + 2^{2015} - 2^3$$

В двоичной системе $2^n$ записывается как единица, за которой следует $n$ нулей.

Число $2^{4028}$ имеет вид: единица и 4028 нулей.

Число $2^{2015}$ имеет вид: единица и 2015 нулей.

При сложении $2^{4028} + 2^{2015}$ получаем число с единицами на позициях 4028 и 2015 (считая от нулевой позиции справа):
$$\underbrace{1\ldots1}_{1 	ext{ единица}} \underbrace{0\ldots0}_{2013 	ext{ нулей}} \underbrace{1\ldots1}_{1 	ext{ единица}} \underbrace{0\ldots0}_{2015 	ext{ нулей}}$$

Теперь вычитаем $2^3 = 8 = 1000_2$.

При вычитании единицы из позиции 3 происходит заём из позиции 2015. Позиции с 3 по 2014 (всего 2012 позиций) заполняются единицами, позиция 2015 становится нулём:
$$\underbrace{1\ldots1}_{1 	ext{ единица}} \underbrace{0\ldots0}_{2013 	ext{ нулей}} \underbrace{1\ldots1}_{2012 	ext{ единиц}} \underbrace{0\ldots0}_{3 	ext{ нуля}}$$

Итого единиц: $1 + 2012 = 2013$.

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

```python
x = 4**2014 + 2**2015 - 8
print(bin(x).count('1'))
```

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

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