Системы счисления

Разбор темы

Позиционные и непозиционные системы 10 класс

В непозиционной римской системе знак всегда значит одно и то же: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000. Знаки складываются, но меньший знак перед большим вычитается: $XIV = 10 + (5 - 1) = 14$, $MCMXCIX = 1000 + 900 + 90 + 9 = 1999$.

В позиционной системе цифра умножается на «вес» разряда — степень основания: $2024_{10} = 2\cdot10^3 + 0\cdot10^2 + 2\cdot10^1 + 4\cdot10^0$. Разряды считаем справа налево, начиная с нуля.

Основание пишут нижним индексом: $101_2$, $101_8$, $101_{16}$ — это три разных числа (5, 65 и 257). В записи числа не может быть цифры, большей или равной основанию: запись $1092_8$ невозможна, потому что цифр 8 и 9 в восьмеричной системе нет.

Шестнадцатеричные цифры-буквы: A = 10, B = 11, C = 12, D = 13, E = 14, F = 15. Их надо помнить наизусть.

Перевод в десятичную систему 10 класс

Пронумеруйте разряды справа налево с нуля, умножьте каждую цифру на $q$ в степени номера разряда и сложите.

$1011_2 = 1\cdot2^3 + 0\cdot2^2 + 1\cdot2^1 + 1\cdot2^0 = 8 + 0 + 2 + 1 = 11$.

$375_8 = 3\cdot64 + 7\cdot8 + 5 = 192 + 56 + 5 = 253$. $2F_{16} = 2\cdot16 + 15 = 47$. $212_3 = 2\cdot9 + 1\cdot3 + 2 = 23$.

Для двоичных чисел удобно выписать «веса» над цифрами: 128, 64, 32, 16, 8, 4, 2, 1 — и сложить веса там, где стоят единицы: $10011101_2 = 128 + 16 + 8 + 4 + 1 = 157$.

Схема Горнера (удобно в уме и в программе): идём по цифрам слева направо, $n = n\cdot q + \text{цифра}$. Для $375_8$: $3 \to 3\cdot8+7 = 31 \to 31\cdot8+5 = 253$.

Перевод из десятичной в любую систему 10 класс

Делим число на основание $q$ с остатком, частное снова делим, пока частное не станет 0. Остатки, записанные снизу вверх (от последнего к первому), и есть ответ.

25 : 2 = 12, остаток 1
12 : 2 = 6,  остаток 0
 6 : 2 = 3,  остаток 0
 3 : 2 = 1,  остаток 1
 1 : 2 = 0,  остаток 1
Читаем снизу вверх: 11001

Значит, $25_{10} = 11001_2$. Проверка: $16 + 8 + 1 = 25$.

Так же в восьмеричную: $100 : 8 = 12$ ост. 4; $12 : 8 = 1$ ост. 4; $1 : 8 = 0$ ост. 1, ответ $144_8$. В шестнадцатеричную остатки 10–15 записывают буквами: $157 : 16 = 9$ ост. 13 (D), $9 : 16 = 0$ ост. 9, ответ $9D_{16}$.

Быстрый способ для двоичной системы — разложить число на степени двойки: $100 = 64 + 32 + 4$, значит единицы стоят в разрядах 6, 5 и 2: $1100100_2$.

Быстрый перевод 2 ↔ 8 ↔ 16: триады и тетрады 10 класс

Так как $8 = 2^3$, каждая восьмеричная цифра — это ровно 3 бита (триада). Так как $16 = 2^4$, каждая шестнадцатеричная цифра — 4 бита (тетрада).

Из двоичной в восьмеричную: разбиваем число на тройки справа налево, слева при необходимости дописываем нули, каждую тройку заменяем цифрой: $1101011_2 = 001\ 101\ 011 = 153_8$.

Из двоичной в шестнадцатеричную: разбиваем на четвёрки справа налево: $1101011_2 = 0110\ 1011 = 6B_{16}$.

Обратно: каждую цифру заменяем тремя (для 8) или четырьмя (для 16) битами, не забывая ведущие нули внутри числа: $5A_{16} = 0101\ 1010 = 1011010_2$; $70_8 = 111\ 000 = 111000_2$.

Между 8 и 16 переходят через двоичную: $753_8 = 111\ 101\ 011_2 = 1\ 1110\ 1011_2 = 1EB_{16}$.

dec bin  oct hex   dec bin  oct hex
 0  0000  0   0     8  1000 10   8
 1  0001  1   1     9  1001 11   9
 2  0010  2   2    10  1010 12   A
 3  0011  3   3    11  1011 13   B
 4  0100  4   4    12  1100 14   C
 5  0101  5   5    13  1101 15   D
 6  0110  6   6    14  1110 16   E
 7  0111  7   7    15  1111 17   F

Двоичная арифметика: сложение, вычитание, умножение 10 класс

Сложение по разрядам справа налево: $0+0=0$, $0+1=1$, $1+1=10$ (пишем 0, 1 переносим), $1+1+1=11$ (пишем 1, 1 переносим).

   1011   (11)
 +  111   ( 7)
 ------
  10010   (18)

Вычитание: $0-0=0$, $1-0=1$, $1-1=0$, $0-1$ — занимаем единицу у старшего разряда, она даёт $10_2$, и $10-1=1$. Пример: $11101_2 - 1011_2 = 10010_2$ ($29 - 11 = 18$).

Умножение — как столбиком в десятичной, только проще: умножаем на 0 или на 1 и складываем сдвинутые строки. $101_2\cdot11_2 = 101 + 1010 = 1111_2$ ($5\cdot3=15$).

Умножить на $2^k$ — дописать справа $k$ нулей ($101_2\cdot 4 = 10100_2$); целочисленно разделить на $2^k$ — отбросить $k$ последних цифр. Так же в любой системе: умножение на $q$ дописывает ноль.

Проверяйте себя переводом в десятичную: ошибку в переносе так заметить легче всего.

Сравнение чисел и подсчёт единиц 10–11 класс

Чтобы сравнить числа в разных системах, переведите их в одну систему (обычно в десятичную или двоичную). $1100100_2 = 100$, $143_8 = 99$, $66_{16} = 102$.

Чем больше основание, тем больше «весит» та же запись: $101_{16} > 101_{10} > 101_8 > 101_2$.

Число разных $n$-значных записей в системе $q$ — $q^n$, наибольшее $n$-значное число — $q^n - 1$: например, $777_8 = 8^3 - 1 = 511$, $FF_{16} = 255$, $11111111_2 = 255$.

Количество единиц: переведите число в двоичную и посчитайте. Для выражений со степенями пользуйтесь шаблонами: $2^n$ — одна единица; $2^n - 1$ — $n$ единиц; $2^n - 2^m$ — $n-m$ единиц. Степени 4 и 8 сводятся к двойке: $4^k = 2^{2k}$, $8^k = 2^{3k}$.

Чётность: двоичное число чётно, если оканчивается на 0. В системе с основанием $q$ последняя цифра — это остаток от деления числа на $q$.

Отрицательные числа и диапазон ячейки 10–11 класс

В $n$ битах без знака помещаются числа от $0$ до $2^n - 1$: в байте от 0 до 255.

Со знаком старший бит означает знак (0 — плюс, 1 — минус), диапазон от $-2^{n-1}$ до $2^{n-1}-1$: в байте от $-128$ до $127$.

Прямой код — модуль числа плюс бит знака. Обратный код отрицательного числа — инвертировать все биты модуля. Дополнительный код — обратный код плюс 1, или сразу $2^n - x$. Компьютер хранит отрицательные целые именно в дополнительном коде, потому что тогда вычитание сводится к сложению.

Пример: $-45$ в 8 битах. $45 = 00101101$, инверсия $11010010$, плюс 1: $11010011$. Проверка: $256 - 45 = 211 = 11010011_2$.

Системы счисления в Python 10–11 класс

bin(n), oct(n), hex(n) возвращают строку с префиксом: bin(10) → '0b1010', oct(10) → '0o12', hex(255) → '0xff'. Префикс убирают срезом [2:].

int(s, base) переводит строку из системы с основанием от 2 до 36 в целое: int('ff', 16) → 255, int('212', 3) → 23.

format(n, '08b') даёт двоичную запись ровно из 8 цифр с ведущими нулями; 'o' и 'X' — восьмеричная и шестнадцатеричная (заглавные буквы).

bin(n).count('1') — количество единиц в двоичной записи. Ручной перевод — цикл с n % q и n // q (см. панель кода).