Системы счисления языка Си

Описание систем счисления

Система счисления - это метод записи чисел при помощи символов (Например: цифр).

Системы счисления бывают двух видов:

• позиционными
• непозиционными

В позиционных системах значение числа зависит от позиции в которой находится цифра. Для примера, в числе 1050 цифра 5 означает количество десятков, в числе 1500 - количество сотен. Количество символов, которое имеет система счисления называется основанием. Так в десятичной системе используется 10 символов от 0 до 9, в двоичной - два символа - 0 и 1.

Самыми распространенными позиционными системами являются:

• двоичная (информатика, булева алгебра, программирование)
• десятичная (повсеместное использование)
• восьмеричная (информатика, программирование)
• шестнадцатеричная (информатика, программирование)

Любое число позиционной системы можно записать в развернутом виде. То есть в виде суммы произведений цифр на основание в определенной степени.

подсказка

$385,5 = {3}*{10}^{2} + {8}*{10}^{1} + {5}*{10}^{0} + {5}*{10}^{-1}$

$1011,01 = {1}*{2}^{3} + {0}*{2}^{2} + {1}*{2}^{1} + {1}*{2}^{0} + {0}*{2}^{-1} + {1}*{2}^{-2}$

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

Расширенная запись позволяет перевести любое число из любой системы счисления, в десятичную систему. Если просуммировать записанное выше выражение, то получится:

$1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0 + 0 * 2^{-1} + 1 * 2^{-2} = 8 + 0 + 2 + 1 + 0,0 + 0,2 = 11,2$

Перевод целой части десятичного числа в другую позиционную систему производится следующим образом:

1. Число делится на основание новой системы.
2. Полученный остаток записывается.
3. Полученный от деления результат снова делится на основание новой системы
4. Эти действия повторяются пока результат от деления не станет меньше основания
5. Результат от деления и все остатки записываются в обратном порядке.

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

Хранение чисел в компьютере

Вся информация хранится в памяти компьютера в виде открытых-закрытых p-n переходах. Для программирования состояния этого перехода используется двоичная система счисления (0 - 1). Один разряд двоичного числа (один переход) называется битом. Однако отдельный бит памяти компьютера не имеет своего адреса, т.е. к нему нельзя обратиться как к самостоятельной единице. Минимальная адресуемая единица памяти называется байтом. Байт состоит из 8 бит. С помощью такого количества двоичных разрядов можно закодировать 256 различных целых чисел без знака.

Для хранения чисел со знаком (положительных и отрицательных) старший бит числа отводиться для кодирования знака: 0 – число неотрицательное, 1- отрицательное. Тогда для хранения собственно значения (модуля) числа остается на один бит меньше. Есть три способа хранения знаковых чисел:

• прямой
• обратный
• с дополнительным кодом

подсказка

Перевод в дополнительный код производится следующим образом:

Если число > 0, то Дополнительный код = |число|

Если число < 0, то Дополнительный код = 2^K - |число|, где K - количество разрядов, выделенных для хранения числа.

Для примера, переведем число -5 в восемь битов.

2^8 - 5 = 251 = 251 = 1111 1011

Булева алгебра

Булева алгебра — это раздел математики, посвященный логическим операциям со значениями истинности («истина» и «ложь»), обычно обозначаемыми как 1 и 0 соответственно. Основные операции булевой алгебры логики включают конъюнкцию (И), дизъюнкцию (ИЛИ) и отрицание (НЕ).

В основе булевой алгебры лежат две критически важные концепции:

• Бинарное исчисление. Этот принцип заключается в том, что информация может быть представлена в виде двух элементарных состояний, обычно обозначаемых цифрами 0 и 1. В контексте электроники это означает «выключено» и «включено». Это делает булеву алгебру идеальной для работы с цифровыми системами и электронными схемами, где вся информация кодируется и обрабатывается именно в такой форме.
• Отсутствие отрицательных значений. Данный принцип устанавливает, что в рамках булевой алгебры элементы могут либо существовать, либо не существовать. Отсутствие «серой зоны» неопределенности делает булеву алгебру предельно ясной и предсказуемой, что важно для разработки надежных логических схем и алгоритмов.

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

Конъюнкция (И)

Это операция, которую можно сравнить с функцией логического умножения. Результат конъюнкции двух утверждений истинен только тогда, когда оба утверждения истинны. В символической форме, если у нас есть две булевы переменные A и B, их конъюнкция записывается как A ∧ B. В контексте электронных схем это можно представить как серию переключателей, где ток течет только тогда, когда все переключатели замкнуты.

A	B	A && B (A и B)
0	0	0
0	1	0
1	0	0
1	1	1

Дизъюнкция (ИЛИ)

Это логическое сложение, где результат операции истинен, если хотя бы одно из утверждений истинно. Она обозначается как A ∨ B и представляет цепь, в которой ток течет, если хотя бы один переключатель замкнут. В более широком смысле, дизъюнкция используется для создания условий, где действие выполняется при соблюдении хотя бы одного из нескольких критериев.

A	B	A || B (A или B)
0	0	0
0	1	0
1	0	0
1	1	1

Отрицание (НЕ)

Операция, меняющая значение переменной на противоположное. Если A истинно, тогда ¬A (читается как «НЕ A») будет ложно, и наоборот. Это аналог включения переключателя, который прерывает ток в электрической цепи, изменяя ее состояние с «активно» на «неактивно».

A	!A (не А)
0	1
1	0

Исключающее ИЛИ (XOR)

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

A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

Импликация (ЕСЛИ…, ТО…)

Принцип, по которому истинность следствия (B) зависит от истинности условия (A). В символической записи A → B истинно, если из истинного A следует истинное B либо когда A ложно вне зависимости от B.

A	B	A -> B
0	0	1
0	1	1
1	0	0
1	1	1

Внимание !

Из истины всегда следует истина. Из лжи может следовать истина или ложь.

Эквивалентность (ТОГДА И ТОЛЬКО ТОГДА)

Это отношение между двумя утверждениями, которое говорит о том, что они имеют одинаковую истинностную оценку. В символическом виде A ↔ B показывает, что A и B или оба истинны, или оба ложны.

A	B	A <-> B
0	0	1
0	1	0
1	0	0
1	1	1

Побитовые операции

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

A = 65, B = 35. Найдем чему равны X = A&B и A|B.

Бит	7	6	5	4	3	2	1	0
A	0	1	0	0	0	0	0	1
B	0	0	1	0	0	0	1	1
&	0	0	0	0	0	0	0	1
|	0	1	1	0	0	0	1	1

Кроме логических побитовых операций есть еще побитовые сдвиги. Операторы сдвига << и >> сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в двоичном дополнительном коде и необходимо поддерживать знаковый бит). Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.

x = 7 00000111 (7)

x = x >> 1 00000011 (3)

x = x << 1 00000110 (6)

x = x << 5 11000000 (-64)

x = x >> 2 11110000 (-16)

Самостоятельная работа

Вопросы для самопроверки

1. Какое минимальное число без знака поместиться в 1 байт?
2. Какое максимальное число без знака поместиться в 1 байт?
3. Какое минимальное число со знаком поместиться в 1 байт?
4. Какое максимальное число со знаком поместиться в 1 байт?

Задачи

Задача 1

Прибор имеет три датчика и может работать, если два из них исправны. Записать в виде формулы ситуацию «авария».

Решение

A – «Датчик № 1 неисправен».

B – «Датчик № 2 неисправен».

C – «Датчик № 3 неисправен».

Аварийный сигнал: X – «Неисправны два датчика».

Составим логическую формулу X = A&&B || A&&C || B&&C

Задача 2

Чему равно X = A&&B + !A&&B + !B

Решение

Составим таблицу истинности

Задача 3

Упростить формулу a & (a→b)&(a→!b)

Решение

a & (a → b)&(a → !b)

избавляемся от импликаций => a & (!a + b) & (!a + !b)

выполняем логическое умножение => (a & !a + a & b) & (!a + !b)

упрощаем = (0 + a & b) & (!a + !b)

раскрываем скобки = a & b & (!a +!b)

раскрываем скобки = a & b & !a + a & b & !b = 0 + 0 = 0

Задания

1. Перевести из 10 в 16 систему число 12345678.
2. Записать в виде логического выражения фразу: "Сгущенного молока и меда и можно без хлеба".
3. Доказать тождества А → В =!A||B, А ↔︎ В = (A && B) || (!A && !B)
4. Найти эквивалент для ⊕?