Битовое представление чисел и операции с ними
Содержание
Двочиная запись числа
Для начала надо понять(или вспомнить), что числа в памяти компьютера имеют двоичное представление. $100_{10} = 1100100_2$
$55_{10} = 110111_2$
$256_{10} = 100000000_2$
Порядок бит
Допустим, есть задача, сформулированная следующим образом: <<Найдите последний бит числа>>. Первым делом мы зададим вопрос, а где у числа первый бит? Если бы вопрос был сформулирован в терминах страших/младших битов, то все сомнения бы отпали.
Дело в том, что может быть и так, и так. В зависимости от архитектуры операционной системы порядок бит при записи их в памяти будет разным. Различают big-endian и little-endian.
При схеме little-endian сначала идут младшие биты. Например, число $100_{10}$ записывалось в двоичной записи так: $0010011$.
При записи в формате big-endian сначала идут старшие биты. В абзаце выше все примеры даны в big-endian формате.
Если в условиях задачи нельзя однозначно определить требуемый формат записи, то надо следовать следующему алгоритму:
- Внимательно посмотреть на тесты и попробовтаь определить из них формат.
- Только в случае, если предыдущий шаг не сработал, обратиться к преподавателям за дополнительным примером.
Операции с битами
Операции с числами в двоичной записи делаются легко и просто с помощью двочиных сдвигов. Во-первых, осознаем, как выглядит ``1 << n``. Это просто единица, у которой справа $n$ нулей и слева тоже все нули. Напомним простейшие битовые операции. Тут $a$ и $b$ будут обозначать отдельные биты. Все операции производятся побитово в масштабе числа.
- a & b = 1 $\Leftrightarrow$ a = 1 и b = 1. AND
- a | b = 1 $\Leftrightarrow$ a = 1 или b = 1. OR
- a ^ b = 1 $\Leftrightarrow$ $a \neq b$. XOR
- ~a = 0 $\Leftrightarrow$ a = 1, ~a = 1 $\Leftrightarrow$ a = 0. Инверсия бита
Примеры
- $13$ & $7$ = $1101_2$ & $0111_2$ = $0101_2$ = $5$
- $17$ | $10$ = $10001_2$ | $01010_2$ = $11011_2$ = $27$
- $17$ ^ $9$ = $10001_2$ ^ $01001_2$ = $11000_2$ = $24$
Выделить i-й бит числа
Сразу скажем, что $i$-й, начиная с младших бит, нумерация с нуля. Пусть исходное число равно $A$.
((1 << i) & A) == 0
$\Leftrightarrow$ i-й бит равен нулю
Пример:
выделить 2-й бит в числе 21:
21 => 10101_2
10101 & (1 << 2) == 10101 & 00100 = 00100 != 0
Выставить i-й бит числа в единицу
То есть надо сделать так, что на $i$-й позиции битовой записи числа стояла единица.
A |= (1 << i)
Инвертировать все биты числа
A = ~A
Получить число, состоящее из k единиц
(1 << k) - 1
Если такое число сдвинуть на несколько битов влево, то получим маску из $k$ единиц, которой можно выделять (с помощью побитового "И") произвольные k бит числа.
Автор конспекта: Полина Романченко
По всем вопросам пишите в telegram @Romanchenko