Битовое представление чисел и операции с ними: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «==Двочиная запись числа== Для начала надо понять(или вспомнить), что числа в памяти компью...»)
 
Строка 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. Внимательно посмотреть на тесты и попробовтаь определить из них формат.
  2. Только в случае, если предыдущий шаг не сработал, обратиться к преподавателям за дополнительным примером.

Операции с битами

Операции с числами в двоичной записи делаются легко и просто с помощью двочиных сдвигов. Во-первых, осознаем, как выглядит ``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 бит числа.