💡 Ключевая идея

Представьте, что вы учите новый язык программирования. Синтаксис может отличаться, но логика остается той же. Точно так же и с системами счисления — принципы сложения, вычитания, умножения и деления универсальны. Меняются только "слова" (цифры) и правила их комбинирования.

🎯 Для чего это нужно?

В начальной школе для обучения счёту используют таблицы сложения и умножения. Подобные таблицы можно составить для любой позиционной системы счисления — и это именно то, чем мы займемся!

🔢 Алгоритм сложения

Чтобы в системе счисления с основанием q получить сумму S двух чисел A и B, надо просуммировать образующие их цифры по разрядам i справа налево:

• Если a_i + b_i < q, то s_i = a_i + b_i, старший (i + 1)-й разряд не изменяется
• Если a_i + b_i ≥ q, то s_i = a_i + b_i – q, старший (i + 1)-й разряд увеличивается на 1

🔢 Алгоритм вычитания

Чтобы в системе счисления с основанием q получить разность R двух чисел A и B, надо вычислить разности образующих их цифр по разрядам i справа налево:

• Если a_i ≥ b_i, то r_i = a_i – b_i, старший (i + 1)-й разряд не изменяется
• Если a_i < b_i, то r_i = a_i – b_i + q, старший (i + 1)-й разряд уменьшается на 1 (выполняется заём в старшем разряде)

🤔 Вопрос для размышления

Сможешь объяснить младшему брату или сестре, почему при вычитании в восьмеричной системе из 5 нельзя вычесть 6 без заёма из старшего разряда?

🔢 Умножение многозначного числа на однозначное

Чтобы в системе счисления с основанием q получить произведение M многозначного числа A и однозначного числа b, надо вычислить произведения b и цифр, образующих число A, по разрядам i справа налево:

• Если a_i · b < q, то m_i = a_i · b, старший (i + 1)-й разряд не изменяется
• Если a_i · b ≥ q, то m_i = a_i · b mod q, старший (i + 1)-й разряд увеличивается на a_i · b div q (где div — операция целочисленного деления)

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

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

⚠️ Особенность деления

Деление нельзя свести к поразрядным операциям над цифрами, составляющими число. Деление чисел в системе счисления с произвольным основанием q выполняется так же, как и в десятичной системе счисления — методом "деления уголком".

Пример деления в восьмеричной системе

  2 6 4 0₈ | 1 7₈
- 1 7₈     |_______
  _____    | 1 4 0₈
    7 4₈
  - 7 4₈
  _____
      0

Проверка: 1 7₈ = 15₁₀, 2 6 4 0₈ = 1440₁₀, 1 4 0₈ = 96₁₀
1440₁₀ ÷ 15₁₀ = 96₁₀ ✓

🤔 Вопрос для размышления

Как бы ты объяснил процесс деления тому, кто знаком только с делением в десятичной системе? В чем ключевое сходство?

✨ Элегантность двоичной арифметики

Обратите внимание на элегантность: умножение на 1 не меняет число, на 0 — обнуляет. Именно поэтому процессоры могут выполнять операции с огромной скоростью — логика предельно проста!

  1 0 1 1 1 1 0 1₂
-     1 0 0 0 0₂
_______________
  1 0 1 0 1 0 1₂

🔑 Ключевое наблюдение

Обратите внимание на закономерность:

2¹ = 10₂ = 1 + 1
2² = 100₂ = 11₂ + 1
2³ = 1000₂ = 111₂ + 1
2⁴ = 10000₂ = 1111₂ + 1

Общая формула:

2ⁿ = 1̲0̲…̲0̲ = 1̲…̲1̲ + 1
     └─n─┘   └n┘

📐 Формулы для натуральных n и m (где n > m)

2ⁿ + 2ᵐ = 1̲0̲…̲0̲ + 1̲0̲…̲0̲ = 1̲0̲…̲0̲1̲0̲…̲0̲
          └─n─┘   └─m─┘   └n-m-1┘└─m─┘

2ⁿ - 2ᵐ = 1̲…̲1̲ + 1 - (1̲…̲1̲ + 1) = 1̲…̲1̲ - 1̲…̲1̲ = 1̲…̲1̲0̲…̲0̲
          └─n─┘     └─m─┘       └─n─┘ └─m─┘   └n-m┘└─m─┘

Пример 1. Количество единиц в двоичной записи

Задача: Найти количество единиц в двоичной записи числа:

2⁴⁰⁰⁰ + 4²⁰¹⁶ + 2²⁰¹⁸ - 8⁶⁰⁰ + 6

Решение:

Шаг 1: Преобразуем все к степеням двойки

4²⁰¹⁶ = (2²)²⁰¹⁶ = 2²·²⁰¹⁶ = 2⁴⁰³²
8⁶⁰⁰ = (2³)⁶⁰⁰ = 2¹⁸⁰⁰
6 = 4 + 2 = 2² + 2¹

Исходное выражение:

2⁴⁰⁰⁰ + 4²⁰¹⁶ + 2²⁰¹⁸ - 8⁶⁰⁰ + 6 = 
= 2⁴⁰⁰⁰ + 2⁴⁰³² + 2²⁰¹⁸ - 2¹⁸⁰⁰ + 2² + 2¹

Шаг 2: Перепишем в порядке убывания степеней:

2⁴⁰³² + 2⁴⁰⁰⁰ + 2²⁰¹⁸ - 2¹⁸⁰⁰ + 2² + 2¹

Шаг 3: Используем формулы для разностей

• 2⁴⁰³² дает 1 единицу
• 2⁴⁰⁰⁰ дает 1 единицу
• 2²⁰¹⁸ - 2¹⁸⁰⁰ = цепочка из (2018 - 1800) = 218 единиц
• 2² дает 1 единицу
• 2¹ дает 1 единицу

Ответ: 1 + 1 + 218 + 1 + 1 = 222 единицы

Без единого вычисления! Просто анализ структуры двоичного представления.

Пример 2. Количество цифр при переводе

Задача: Найти количество цифр в восьмеричной записи числа:

2²⁹⁹ + 2²⁹⁸ + 2²⁹⁷ + 2²⁹⁶

Решение:

Двоичное представление исходного числа имеет вид:

1111̲0̲…̲0̲
    └296┘

Всего в этой записи 300 двоичных символов (4 + 296).

При переводе двоичного числа в восьмеричную систему каждая триада (группа из 3 двоичных цифр) исходного числа заменяется одной восьмеричной цифрой.

Следовательно:

300 ÷ 3 = 100

Ответ: восьмеричное представление исходного числа состоит из 100 цифр.

Применение в жизни: Такие расчеты используются при оценке размера данных в памяти или при оптимизации алгоритмов шифрования.

🤔 Вопрос для размышления

Где в реальной жизни может пригодиться умение быстро определять количество разрядов в различных системах счисления? Подумай о работе с памятью компьютера, сетевыми адресами или криптографией.

Задача 7. Восстановление цифр

В примерах на сложение восстановите неизвестные цифры, обозначенные знаком вопроса, определив вначале, в какой системе счисления эти числа записаны:

  2 ? 2 1
+   1 2 3 ?
___________
  ? 2 0 3 ?

  5 ? 5 5
+   ? 3 2 7
___________
  ? 1 6 ?

  2 1 ? 0 2
+ ? 1 2 1 2
___________
  ? 2 ? 0 2 1

Задача 8. Сравнение чисел

Даны 4 целых числа, записанные в двоичной системе счисления:

11000000₂, 11000011₂, 11011001₂, 11011111₂

Вопрос: Сколько среди них чисел, больших, чем AB₁₆ + 25₈?

Задача 9. Подсчет единиц (★)

Сколько единиц в двоичной записи числа 4²⁰¹⁴ + 2²⁰¹⁵ - 9?

Подсказка: используйте свойства степеней двойки!

Задача 10. Сложная задача на единицы (★★)

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

8⁴⁰²⁴ - 4¹⁶⁰⁵ + 2¹⁰²⁴ - 126

Задача 11. Подсчет цифр (★)

Сколько цифр в восьмеричной записи числа 2¹⁰²⁴ + 2¹⁰²⁶?

Задача 12. Первая цифра (★)

Какая первая цифра в шестнадцатеричной записи числа 2¹⁰²⁴ + 2¹⁰²⁵?