14.01 Арифметические выражения

Решение программой

Для подсчёта количества единиц в двоичной записи числа необходимо написать алгоритм перевода исходного числа в двоичную систему счисления. Для перевода реализуем в программе стандартный алгоритм перевода числа из десятичной системы счисления в другую. Потом подсчитаем количество единиц при помощи метода count(). Также можно использовать функцию bin() для перевода числа в двоичную систему счисления.

# Способ 1
# Исходное выражение
a = 4**2015 + 8**405 - 2**150 - 122

# Переменная для хранения числа в двоичной системе в виде строки
s = ’’

# Перевод числа из десятичной системы в двоичную
while a > 0:
    # Получаем последнюю цифру (остаток от деления на 2) и добавляем её в начало строки
    s = str(a % 2) + s
    # Отбрасываем последнюю цифру (целочисленное деление на 2)
    a //= 2

# Подсчёт и вывод количества единиц ’1’ в двоичной записи числа
print(s.count(’1’))

# Способ 2
# Прямое преобразование числа в двоичную строку с помощью bin()
a = bin(4**2015 + 8**405 - 2**150 - 122)[2:]

# Подсчёт и вывод количества единиц ’1’ в двоичной записи числа
print(a.count(’1’))

Решение руками:

Каждое из чисел либо приведем к виду . После чего внутри двоичной сс выполним все арифметические операции и получим ответ.

В результате сложения первых двух чисел получаем число, в котором 4031 цифра, первая цифра слева - единица и 1216 цифра справа - единица, остальные - нули. Вычтем число, в котором 151 цифра: 1 единица слева и 150 нулей, заняв из 1216 разряда.

    100...0100...00000...000
   -               100...000
    ------------------------
    100...0011...11000...000

Таким образом 1216 разряд заменится на 0, цифры от 1216 до 151 разряда заменятся на единицу, в 151 разряде произойдет вычитание и останется ноль, остальные цифры останутся неизменны. Вычтем число, в котором 8 цифр: 1 единица слева и 7 нулей, заняв из 151 разряда.

    100...0011...11000...000000000
   -                      10000000
    ------------------------------
    100...0011...10111...100000000

Таким образом 151 разряд заменится на 0, цифры от 151 до 8 разряда заменятся на единицу, в 8 разряде произойдет вычитание и останется 0, остальные цифры останутся неизменны. Выполним операцию сложения, зная, что .

    100...0011...10111...100000000
   +                           110
    ------------------------------
    100...0011...10111...100000110

Тогда единицы будут от 1216 разряда до 151 разряда невключительно (1065 единиц), от 150 до 8 разряда невключительно (142 единицы), одна в начале числа и две в конце - суммарно 1210 единиц.