Битовое представление чисел и операции с ними: различия между версиями
(Новая страница: «==Двочиная запись числа== Для начала надо понять(или вспомнить), что числа в памяти компью...») |
|||
Строка 37: | Строка 37: | ||
Сразу скажем, что $i$-й, начиная с младших бит, нумерация с нуля. Пусть исходное число равно $A$. | Сразу скажем, что $i$-й, начиная с младших бит, нумерация с нуля. Пусть исходное число равно $A$. | ||
− | <code>(1 << i & A) == 0</code> $\Leftrightarrow$ i-й бит равен нулю | + | <code>((1 << i) & A) == 0</code> $\Leftrightarrow$ i-й бит равен нулю |
'''Пример:''' | '''Пример:''' | ||
Строка 46: | Строка 46: | ||
<code>10101 & (1 << 2) == 10101 & 00100 = 00100 != 0</code> | <code>10101 & (1 << 2) == 10101 & 00100 = 00100 != 0</code> | ||
+ | |||
+ | ===Выставить i-й бит числа в единицу=== | ||
+ | То есть надо сделать так, что на $i$-й позиции битовой записи числа стояла единица. | ||
+ | |||
+ | <code>A |= (1 << i)</code> | ||
+ | |||
+ | ===Инвертировать все биты числа=== | ||
+ | |||
+ | <code> A = ~A</code> | ||
+ | |||
+ | ===Получить число, состоящее из k единиц=== | ||
+ | |||
+ | <code> (1 << k) - 1</code> | ||
+ | |||
+ | Если такое число сдвинуть на несколько битов влево, то получим маску из $k$ единиц, которой можно выделять (с помощью побитового "И") произвольные k бит числа. |
Версия 13:13, 7 февраля 2020
Содержание
Двочиная запись числа
Для начала надо понять(или вспомнить), что числа в памяти компьютера имеют двоичное представление. $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 бит числа.