Системы счисления и точность вычислений

Что такое система счисления

Система счисления — это способ записи чисел с помощью набора символов и правил. В позиционной системе значение цифры зависит от её места (позиции) в записи. Основание системы показывает, сколько различных цифр в ней используется. В двоичной системе их две, в десятичной — десять, в шестнадцатеричной — шестнадцать.

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

Перевод между системами

Чтобы перевести число в десятичную систему, каждую цифру умножают на основание в степени, равной номеру её позиции, и складывают полученные слагаемые.

Двоичное 1011 в десятичное: 1*8 + 0*4 + 1*2 + 1*1 = 11 Двоичное 11111111 в десятичное: сумма степеней двойки от 0 до 7 = 255

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

Дробные числа и точность

Многие десятичные дроби нельзя точно представить в двоичной системе. Например, число 0,1 в двоичной записи бесконечно, подобно тому как дробь 1/3 бесконечна в десятичной. Поэтому компьютер хранит такие числа приближённо, и при вычислениях накапливается ошибка округления.

0,1 + 0,2 в компьютере может дать 0,30000000000000004 Причина: числа 0,1 и 0,2 хранятся не точно, а приближённо

Числа с плавающей запятой имеют ограниченное число значащих цифр, поэтому очень большие и очень маленькие значения тоже теряют точность при хранении и расчётах.

Целые числа и переполнение

Целые числа компьютер хранит точно, но в ограниченном диапазоне, который зависит от числа отведённых разрядов. Если результат вычисления выходит за этот диапазон, происходит переполнение, и значение становится неверным. Чем больше разрядов отводится под число, тем шире диапазон.

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

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

Нестандартные задачи: смотрим на запись числа

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

Оригинальная задача на разворот битов

Возьмём число 26: его обычная двоичная запись 11010. Развернём порядок цифр: 01011. Как число эта запись равна 1011₂ = 11. Повторный разворот обычной записи 1011 даёт 1101₂ = 13, а не 26: потерялся ведущий ноль промежуточной записи.

Если же заранее задано пять бит и ноль сохраняется, повторный разворот 01011 возвращает 11010. Поэтому до решения уточните, разворачивается ли минимальная запись натурального числа или строка фиксированной длины.

Сколько симметричных записей

Найдём число двоичных палиндромов длиной 6 без ведущего нуля. Первая и последняя цифры обязаны быть 1. Вторую и третью выбираем свободно, остальные определяются зеркально. Ответ: 2² = 4. Это 100001₂, 101101₂, 110011₂, 111111₂ — числа 33,45,51,63.

Неизвестное основание

Если 23 в системе с основанием b равно десятичному 17, то 2b + 3 = 17, откуда b = 7. Проверка допустимости: все цифры должны быть меньше основания; 2 и 3 меньше 7, условие выполнено.

Проверьте себя: может ли запись 29 иметь основание 8? Нет, цифры 9 в восьмеричной системе не существует. Не решайте уравнение для основания, забыв про набор допустимых цифр. При подсчёте количества чисел включайте обе границы диапазона, если они указаны словами «не меньше» и «не больше».

Справочные материалы: Что такое система счисления — исходная тема. Связанные уроки: Алгоритмы и их эффективность, Трассировка алгоритма по шагам.

Кратко о главном

• Система счисления задаётся основанием и набором цифр.
• Компьютер использует двоичную систему, программисты — шестнадцатеричную.
• Перевод в десятичную — через сумму цифр на степени основания.
• Дробные числа хранятся приближённо, что вызывает ошибки округления.