Системы счисления. Целые числа

Запись, переводы, группировка, арифметика, делимость, основание

Число в системе счисления с основанием b — это сумма цифр, умноженных на степени b:

Считать это удобнее схемой Горнера слева направо: на каждом шаге n = n·b + цифра. Это же — готовый алгоритм перевода b → 10.

вручную// 3A7₁₆ → десятичная (A = 10), схема Горнера
старт      n = 0
цифра 3 :  n = 0·16 + 3   = 3
цифра A :  n = 3·16 + 10  = 58
цифра 7 :  n = 58·16 + 7  = 935

// проверка: 3·256 + 10·16 + 7 = 768 + 160 + 7 = 935

python# b → 10 (схема Горнера)
s, b = "3A7", 16
n = 0
for c in s:
    n = n*b + int(c, b)   # int('A',16) = 10
# n == 935  (или сразу int("3A7", 16))

Алгоритм. Делим число на b, остатки — это цифры. Собираем их снизу вверх: последний остаток — старшая цифра.

вручную// 935 → шестнадцатеричная: делим на 16, остатки снизу вверх
935 : 16 = 58   ост 7      ↑
 58 : 16 =  3   ост 10 (A) ↑
  3 : 16 =  0   ост 3      ↑

935₁₀ = 3A7₁₆

// ещё: 2026 → семеричная
2026:7=289 ост 3;  
289:7=41 ост 2;  
41:7=5 ост 6;  
5:7=0 ост 5
2026₁₀ = 5623₇

python# 10 → b (деление с остатком)
import string
D = string.digits + string.ascii_uppercase

def to_base(n, b):
    s = ""
    while n:
        s = D[n % b] + s   # остаток = цифра
        n //= b
    return s or "0"
# to_base(935,16)=="3A7";  to_base(2026,7)=="5623"

Так как  4 = 2² , 8 = 2³ и 16 = 2⁴, перевод между этими системами идёт без десятичного посредника: бьём двоичную запись на группы по 2 (для 4), 3 (для 8) или 4 (для 16) справа налево и заменяем каждую группу одной цифрой. Это нужно уметь устно — экономит время на отборе.

пример// 11010110₂ → hex: группы по 4 справа
1101 0110₂  =  D 6  =  D6₁₆
 13   6

// то же → oct: группы по 3 справа (слева дополнили нулём)
011 010 110₂  =  3 2 6  =  326₈

Складывать и умножать можно «столбиком» в самой системе: алгоритм тот же, что в десятичной, только перенос возникает при достижении b, а не 10.

пример// 7₈ + 5₈  (перенос при достижении 8)
7 + 5 = 12₁₀ = 1·8 + 4   →   пишем 4, переносим 1
7₈ + 5₈ = 14₈

// 1A₁₆ + 2F₁₆
A + F = 10 + 15 = 25 = 1·16 + 9   →   9, перенос 1
1 + 2 + 1 = 4
1A₁₆ + 2F₁₆ = 49₁₆

Школьные признаки обобщаются на любое основание b:

признакина b−1  —  по сумме цифр              (как «на 9» в десятичной)
на b+1  —  по знакочередующейся сумме    (как «на 11»)
на делитель b  —  по последней цифре      (как «на 2» и «на 5»)

// пример: делится ли F0F₁₆ на 15?  (15 = 16−1)
сумма цифр:  F + 0 + F = 15 + 0 + 15 = 30,   30 делится на 15  →  да
// проверка: F0F₁₆ = 3855 = 15 · 257 ✓

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

пример// 15_b + 15_b = 32_b — найти b.  Цифры < b ⇒ b > 5
(b + 5) + (b + 5) = 3b + 2
2b + 10 = 3b + 2   →   b = 8   (5 < 8 ✓)

// умножение: 5_b · 3_b = 21_b
5 · 3 = 15 = 2b + 1   →   b = 7   (цифры 5, 3, 2, 1 < 7 ✓)

Программой: перебрать b от (макс. цифра + 1) и проверить равенство

Float-логарифм даёт ошибку ±1 на границах (степенях основания), поэтому число разрядов надёжнее получить, деля на b до нуля и считая шаги. Частоту цифр — счётчиком по записи.

пример// число разрядов
2¹⁰⁰ в десятичной:  31 разряд

// частота цифр
2026₁₀ = 11111101010₂   →   единиц: 8,   нулей: 3