7. Чем отличается логический сдвиг двоичного кода от арифметического сдвига?
При логическом сдвиге значение последнего бита по направлению сдвига теряется (копируясь в бит переноса), а первый приобретает нулевое значение.
Арифметический сдвиг аналогичен логическому, но число считается знаковым, представленным в дополнительном коде. Так, при правом сдвиге старший бит сохраняет своё значение. Левый арифметический сдвиг идентичен логическому.
Арифметический сдвиг:
Вывод: арифметический сдвиг отличается от логического тем, что он не изменяет значение старшего бита, и предназначен для чисел со знаком.
8. Как изменяется значение числа при арифметическом сдвиге на 1 двоичный разряд влево?
При арифметическом сдвиге сдвиг влево соответствует умножению на 2 (в общем случае — на основание системы счисления).
9. Как изменяется значение числа при арифметическом сдвиге на 1 двоичный разряд вправо?
При арифметическом сдвиге сдвиг вправо соответствует делению на 2 (в общем случае — на основание системы счисления).
10. В каком порядке следует выполнять действия для получения прямого кода двоичного целого числа из дополнительного кода? (НЕ УВЕРЕН)
Прямой обратный и дополнительный код - это модели представления целых чисел , как положительных, так и отрицательных. Во всех трех кодах старший разряд указывает на знак числа и он равен единице, если число отрицательное и нулю в противном случае. Остальные разряды содержат представление модуля числа. Различие между кодами наблюдается именно в способах представления модуля. Для положительного числа модуль во всех трех кодах представляется одинаково - это просто естественная запись двоичного числа. Для отрицательных чисел, в обратном коде это просто поразрядная инверсия прямого кода, а в дополнительном - к обратному коду, как к числу, просто прибавляется единица.
Вычесть единицу и инвертировать, кроме бита знака.
Побитовые операции
Побитовые операции (англ. bitwise operations) — операции, производимые над цепочками битов. Выделяют два типа побитовых операций: логические операции и побитовые сдвиги.
Принцип работы
Логические побитовые операции
Битовые операторы И [math](AND,\ \&)[/math] , ИЛИ [math](OR,\ \mid)[/math] , НЕ [math](NOT,\ \sim)[/math] и исключающее ИЛИ [math](XOR,\ $\textasciicircum$,\ \oplus)[/math] используют те же таблицы истинности, что и их логические эквиваленты.
Побитовое И
Побитовое И используется для выключения битов. Любой бит, установленный в [math]0[/math] , вызывает установку соответствующего бита результата также в [math]0[/math] .
| & |
|---|
| 11001010 11100010 |
| 11000010 |
Побитовое ИЛИ
Побитовое ИЛИ используется для включения битов. Любой бит, установленный в [math]1[/math] , вызывает установку соответствующего бита результата также в [math]1[/math] .
| | |
|---|
| 11001010 11100010 |
| 11101010 |
Побитовое НЕ
Побитовое НЕ инвертирует состояние каждого бита исходной переменной.
| ~ |
|---|
| 11001010 |
| 00110101 |
Побитовое исключающее ИЛИ
Исключающее ИЛИ устанавливает значение бита результата в [math]1[/math] , если значения в соответствующих битах исходных переменных различны.
| ^ |
|---|
| 11001010 11100010 |
| 00101000 |
Побитовые сдвиги
Операторы сдвига [math]\lt \lt [/math] и [math]<\gt \gt >[/math] сдвигают биты в переменной влево или вправо на указанное число. При этом на освободившиеся позиции устанавливаются нули (кроме сдвига вправо отрицательного числа, в этом случае на свободные позиции устанавливаются единицы, так как числа представляются в двоичном дополнительном коде и необходимо поддерживать знаковый бит).
Сдвиг влево может применяться для умножения числа на два, сдвиг вправо — для деления.
x = 7 // 00000111 (7) x = x >> 1 // 00000011 (3) x = x // 00000110 (6) x = x // 11000000 (-64) x = x >> 2 // 11110000 (-16)
В языке программирования Java существует также оператор беззнакового битового сдвига вправо [math]\gt \gt \gt [/math] . При использовании этого оператора на освободившиеся позиции всегда устанавливаются нули.
x = 7 // 00000111 (7) x = x // 11100000 (-32) x = x >>> 2 // 00111000 (56)
Применение
Сложные операции
Определение знака числа
Пусть дано число [math]x[/math] . Поскольку при сдвиге вправо на освобождающиеся позиции устанавливается бит знака, знак числа [math]x[/math] можно определить, выполнив сдвиг вправо на всю длину переменной:
int32 getSign(x: int32): if x != 0: mask = 1 else: mask = 0 return mask | (x >> 31) // результатом будет -1, 0, или +1 // для отрицательного, равного нулю и положительного числа x соответственно
Используя побитовые операции можно также узнать, различны ли знаки двух переменных [math]x[/math] и [math]y[/math] . Если числа имеют различный знак, то результат операции XOR, произведенной над их знаковыми битами, будет единицей. Поэтому неравенство [math](x \oplus y) \lt 0[/math] будет верно в том случае, если числа [math]x[/math] и [math]y[/math] разного знака.
Вычисление модуля числа без использования условного оператора
Пусть дано число [math]x[/math] . Если [math]x[/math] положительно, то [math]mask = 0[/math] , и [math](x + mask) \oplus mask = x[/math] . В случае, если [math]x[/math] отрицательно, [math]mask = -1[/math] . Тогда получается, что мы работаем с числом [math]x[/math] так, как будто оно представлено в коде со сдвигом с тем отличием, что у нас знаковый бит принимает значение [math]1[/math] для отрицательных чисел, а [math]0[/math] — для положительных.
int32 abs1(x: int32): mask = x >> 31 return (x + mask) XOR mask int32 abs2(x: int32): mask = x >> 31 return (x + mask) XOR mask
Нахождение минимума и максимума из двух чисел без использования условного оператора
Этот способ корректен только если можно утверждать, что величина [math](x — y)[/math] лежит между граничными значениями типа int.
Пусть даны числа [math]x[/math] и [math]y[/math] разрядности [math]n[/math] . Тогда если [math]x \lt y[/math] , то [math]((x — y) \gt \gt (n — 1)) = -1[/math] , а если [math]x \geqslant y[/math] , то [math]((x — y) \gt \gt (n — 1)) = 0[/math] . Выражение [math]((x — y) \& ((x — y) \gt \gt (n — 1))[/math] принимает значение [math]0[/math] , если [math]x \geqslant y[/math] , и [math](x — y)[/math] , если [math]x \lt y[/math] .
int32 min(x, y: int32): return y + ((x - y) & ((x - y) >> 31)) int32 max(x, y: int32): return x - ((x - y) & ((x - y) >> 31))
Проверка на то, является ли число степенью двойки
Пусть дано число [math]x[/math] . Тогда, если результатом выражения [math](x\ \&\&\ !(x\ \&\ (x — 1)))[/math] является единица, то число [math]x[/math] — степень двойки.
Правая часть выражения [math](!(x\ \&\ (x — 1)))[/math] будет равна единице, только если число [math]x[/math] равно [math]0[/math] или является степенью двойки. Если число [math]x[/math] является степенью двойки, то в двоичной системе счисления оно представляется следующим образом: [math]1\underbrace_[/math] , где [math]n[/math] — показатель степени. Соответственно, выражение [math](x — 1)[/math] будет иметь вид [math]\underbrace_[/math] , и [math]x\ \&\ (x — 1)[/math] равно [math]0[/math] .
Операция логического И в данном выражении отсекает тот случай, когда [math](x = 0)[/math] и не является степенью двойки, но при этом правая часть [math](!(x\ \&\ (x — 1)))[/math] равна единице.
Нахождение младшего единичного бита
Пусть дано число [math]x[/math] и необходимо узнать его младший единичный бит.
Применим к числу [math]x[/math] побитовое отрицание, чтобы инвертировать значения всех его бит, а затем прибавим к полученному числу единицу. У результата первая часть (до младшего единичного бита) не совпадает с исходным числом [math]x[/math] , а вторая часть совпадает. Применив побитовое И к этим двум числам, получим степень двойки, соответствующую младшему единичному биту исходного числа [math](x\ \&\ (\sim x + 1))[/math] .
К такому же результату можно прийти, если сначала отнять от числа [math]x[/math] единицу, чтобы обнулить его младший единичный бит, а все последующие разряды обратить в [math]1[/math] , затем инвертировать результат и применить побитовое И с исходным числом [math](x\ \&\ \sim (x — 1))[/math] .
Нахождение старшего единичного бита
Пусть дано число [math]x[/math] и необходимо узнать его старший единичный бит.
Рассмотрим некоторое число, представим его как [math]0\dots01b \dots b[/math] , где [math]b[/math] — любое значение бита. Тогда, если совершить битовый сдвиг этого числа вправо на [math]1[/math] и произвести побитовое ИЛИ результата сдвига и исходного числа, мы получим результат [math]0\dots011b \dots b[/math] . Если мы повторим эту последовательность действий над полученным числом, но устроим сдвиг на [math]2[/math] , то получим [math]0\dots01111b \dots b[/math] . При каждой следующей операции будем увеличивать модуль сдвига до следующей степени двойки. После некоторого количества таких операций (зависит от разрядности числа) мы получим число вида [math]0\dots01\dots1[/math] . Тогда результатом выполнения действий [math]x — (x \texttt< \gt \gt >1)[/math] будет число, состоящее только из старшего бита исходного числа.
int32 greatestBit(x: int32): power = 1 for i = 1 : x |= x >> power power return x - (x >> 1)
Циклический сдвиг
Пусть дано число [math]x[/math] и надо совершить циклический сдвиг его битов на величину [math]d[/math] . Желаемый результат можно получить, если объединить числа, полученные при выполнении обычного битового сдвига в желаемую сторону на [math]d[/math] и в противоположном направлении на разность между разрядностью числа и величиной сдвига. Таким образом, мы сможем поменять местами начальную и конечную части числа.
int32 rotateLeft(x, d: int32): return (x >> (32 - d)) int32 rotateRight(x, d: int32): return (x >>> d) | (xПодсчет количества единичных битов
Для подсчета количества единичных битов в числе [math]x[/math] можно воспользоваться следующим алгоритмом:
// Для чисел других разрядностей необходимо использовать соответствующие константы. int16 setBitsNumber(x: int16): x = x - ((x >>> 1) & 0x5555) x = (x & 0x3333) + ((x >>> 2) & 0x3333) x = (x + (x >>> 4)) & 0x0F0F return (x * 0x0101) >>> 8Поскольку [math]5555_[/math] равно [math]01010101 01010101_[/math] , результатом операции [math]x\ \&\ 5555_[/math] является число, в котором все нечетные биты соответствуют нечетным битам числа [math]x[/math] . Аналогично, результатом операции [math](x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 5555_[/math] является число, в котором все нечетные биты соответствуют четным битам [math]x[/math] . Четные биты результата в обоих случаях равны нулю.
Мысленно разобьем двоичную запись нашего числа [math]x[/math] на группы по [math]2[/math] бита. Результатом операции [math]x\ \&\ 5555_ + (x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 5555_[/math] будет такое число, что если разбить его двоичную запись на группы по два бита, значение каждой группы соответствует количеству единичных битов в соответствующей паре битов числа [math]x[/math] .
Аналогично, число [math]3333_[/math] равно [math]00110011 00110011_[/math] и операция [math]x = (x\ \&\ 3333_) + (x\ \texttt<\gt \gt \gt >\ 2\ \&\ 3333_)[/math] , примененная к результату, полученному на первом этапе, выполняет подсчет количества единичных битов в блоках по [math]4[/math] . В свою очередь, число [math]\texttt_[/math] равно [math]00001111 00001111_[/math] и операция [math]x = (x\ \&\ \texttt_) + (x\ \texttt<\gt \gt \gt >\ 4\ \&\ \texttt_)[/math] позволяет подсчитать число единичных бит в блоках по [math]8[/math] .
Теперь необходимо просуммировать числа, записанные в блоках по [math]8[/math] битов, чтобы получить искомую величину. Это можно сделать, домножив результат на [math]0101_[/math] [math](1 00000001_)[/math] . Ответ на задачу будет находиться в первых восьми битах произведения. Выполнив сдвиг вправо на [math]8[/math] (для шестнадцатибитных чисел), мы получим долгожданный ответ.
int16 setBitsNumber(x: int16): x = (x & 0x5555) + ((x >>> 1) & 0x5555) x = (x & 0x3333) + ((x >>> 2) & 0x3333) x = (x & 0x0F0F) + ((x >>> 4) & 0x0F0F) return (x * 0x0101) >>> 8Заметим, что операция [math]x\ \&\ 55_ + (x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 55_[/math] равносильна операции [math]x - (x\ \texttt<\gt \gt \gt >\ 1)\ \&\ 55_[/math] , в чем легко убедиться, рассмотрев все числа из двух бит.
В свою очередь, операцию [math](x\ \&\ \texttt_) + ((x\ \texttt<\gt \gt \gt >\ 4)\ \&\ \texttt_)[/math] можно заменить на [math](x + (x\ \texttt<\gt \gt \gt >\ 4))\ \&\ \texttt_[/math] . Эта замена не повлияет на результат, так как максимальное значение в любой группе из четырех битов данного числа равно четырем, то есть требует только трех битов для записи, и выполнение суммирования не повлечет за собой переполнения и выхода за пределы четверок.
Таким образом, мы получили код, приведенный в начале раздела.
Разворот битов
Чтобы получить биты числа [math]x[/math] , записанные в обратном порядке, применим следующий алгоритм.
// Для чисел других разрядностей нужны соответствующие константы. int16 reverseBits(x: int16): x = ((x & 0x5555) >> 1) & 0x5555) // Четные и нечетные биты поменялись местами. x = ((x & 0x3333) >> 2) & 0x3333) // Биты "перетасовываются" группами по два. x = ((x & 0x0F0F) >> 4) & 0x0F0F) // Биты "перетасовываются" группами по четыре. x = ((x & 0x00FF) >> 8) & 0x00FF) // Биты "перетасовываются" группами по восемь. return xБолее подробно про то, что за константы выбраны для данного алгоритма, можно прочитать в разделе подсчет количества единичных битов.
Применение для решения задач
Работа с битовыми масками
Для работы с подмножествами удобно использовать битовые маски. Применяя побитовые операции легко сделать следующее: найти дополнение [math](\sim mask)[/math] , пересечение [math](mask_1\ \&\ mask_2)[/math] , объединение [math](mask_1 \mid mask_2)[/math] множеств, установить бит по номеру [math](mask \mid (1\ \texttt<\lt \lt >\ x))[/math] , снять бит по номеру [math](mask\ \&\ \sim(1\ \texttt<\lt \lt >\ x))[/math] .
Битовые маски используются, например, при решении некоторых задач [1] динамического программирования.
Алгоритм Флойда
Основная статья: Алгоритм Флойда
Алгоритм Флойда–Уоршелла (англ. the Floyd–Warshall algorithm) — алгоритм для нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а если же такой цикл есть, позволяет найти хотя бы один такой цикл. Асимптотическая сложность алгоритма [math] \Theta(n^3) [/math] , также требует [math] \Theta(n^2) [/math] памяти.
Дерево Фенвика
Основная статья: Дерево Фенвика
Дерево Фенвика (англ. Binary indexed tree) — структура данных, которая может выполнять следующие операции:
- изменять значение любого элемента в массиве,
- выполнять некоторую ассоциативную, коммутативную, обратимую операцию [math] \circ [/math] на отрезке [math] [i, j] [/math] .
Данная структура требует [math] O(n) [/math] памяти, а выполнение каждой операции происходит за [math] O(\log n) [/math] .
Функция, позволяющая делать операции вставки и изменения элемента за [math] O(\log n) [/math] , задается следующей формулой [math] F(i) = (i \And (i + 1)) [/math] . Пусть дан массив [math] A = [a_0, a_1, \ldots, a_][/math] . Деревом Фенвика называется массив [math] T [/math] из [math] n [/math] элементов: [math] T_i = \sum\limits_^ a_k[/math] , где [math] i = 0\ldots n - 1 [/math] и [math] F(i) [/math] — функция, которую мы определили ранее.
См. также
- Определение булевой функции
- Сумматор
- Триггеры
Примечания
Источники информации
- Онлайн справочник программиста на С и С++
- Побитовые операторы
- Bit Twiddling Hacks by Sean Eron Anderson
- Habrahabr — Алгоритмы поиска старшего бита
- STP's blog — Counting the number of set bits in an integer
Логический сдвиг
Би́товый сдвиг — изменение позиций битов в слове на одну и ту же величину.
В основной своей массе компьютеры не могут напрямую адресовать биты, которые содержатся группами по 8, 16, 32 битов в словах. Для обеспечения работы с битами существует множество команд, к которым относятся и сдвиги: Все сдвиги похожи друг на друга поведением средних битов: они просто сдвигаются влево или вправо на определённую величину. И различаются поведением крайних битов: одного, который уходит из слова, и второго, который должен появиться в слове.
Логический сдвиг
Логический сдвиг влево
Логический сдвиг вправо
Сдвиг, при котором уходящий бит уходит, не влияя на оставшееся биты, а на место появившегося бита записывается бит 0.
Пример работы операции сдвига:
Пусть у нас есть число 10101010b (в двоичной системе). Если сделать сдвиг влево на 1 бит, то получим число 01010100b Если сделать сдвиг вправо на 1 бит, то получим число 01010101b
В большинстве процессоров уходящий бит сохраняется в флаге переноса. Эта функция широко используется при работе с многобайтовыми числами.
Арифметический сдвиг
Арифметический сдвиг влево
Арифметический сдвиг вправо
При этом сдвиге слово рассматривается не просто как группа битов, а как целое число в дополнительном коде. При сдвиге влево ведёт себя как логический сдвиг, при сдвиге вправо: уходящий бит уходит, не влияя на оставшееся биты, а на место появившегося бита устанавливается бит, соответствующий знаку.
Пример работы операции сдвига:
Пусть у нас есть число 11111010b=−6 (в двоичной системе). Если сделать сдвиг влево на 1 бит, то получим число 11110100b=−12 Если сделать сдвиг вправо на 1 бит, то получим число 11111101b=−3
Легко заметить, что при арифметическом сдвиге сдвиг влево соответствует умножению на 2, а сдвиг вправо делению на 2 (в общем случае — на основание системы счисления). Исключение: −1 >>a 1 = −1 (в общем случае это относится к числам от −1 до −p+1, где p — основание системы счисления).
Схемотехническая реализация операций сдвига очень проста. Именно поэтому эти операции рекомендуют использовать для операций умножения и деления целых чисел на числа равные степени 2 (2, 4, 8, 16, 32, 64 и т. д.).
Битовые операции
Во многих языках программирования допустимы логические операции над битами целых чисел. В отличие от обычных логических операций, результатом выполнения которых является логический тип данных, битовые логические операции просто изменяют целое число согласно определенным правилам. Точнее битовые операции изменяют отдельные биты двоичного представления числа, в результате чего изменяется его десятичное значение.
Например, в языке программирования Паскаль обычные логические операции и логические операции над битами обозначают с помощью одних и тех же ключевых слов: not, and, or, xor . Компилятор определяет, что имелось в виду в зависимости от контекста использования этих слов. Обычные логические операции объединяют два и более простых логических выражения. Например, (a > 0) and (c != b) , (c < a) or(not b) и т.п. В свою очередь побитовые логические операции выполняются исключительно над целыми числами (или переменными, которые их содержат). Например, a and b, a or 8, not 247 .
Как понять побитовые операции
1. Переведем пару произвольных целых чисел до 256 (один байт) в двоичное представление.
6710 = 0100 00112 11410 = 0111 00102
2. Теперь расположим биты второго числа под соответствующими битами первого и выполним обычные логические операции к цифрам, стоящим в одинаковых разрядах первого и второго числа. Например, если в последнем (младшем) разряде одного числа стоит 1, а другого числа — 0, то логическая операция and вернет 0, а or вернет 1. Операцию not применим только к первому числу.
3. Переведем результат в десятичную систему счисления.
01000010 = 26 + 21 = 64 + 2 = 66 01110011 = 26 + 25 + 24 + 21 + 20 = 64 + 32 + 16 + 2 + 1 = 115 00110001 = 25 + 24 + 20 = 32 + 16 + 1 = 49 10111100 = 27 + 25 + 24 + 23 + 22 = 128 + 32 + 16 + 8 + 4 = 188
4. Итак, в результате побитовых логических операций получилось следующее:
67 and 114 = 66 67 or 114 = 115 67 xor 114 = 49 not 67 = 188
Вот еще один пример выполнения логических операций над битами. Проверьте его правильность самостоятельно.
5 and 6 = 4 5 or 6 = 7 5 xor 6 = 3 not 5 = 250
Зачем нужны побитовые логические операции
Глядя на результат побитовых операций, не сразу можно уловить закономерности в их результате. Поэтому непонятно, зачем нужны такие операции. Однако, они находят свое применение. В байтах не всегда хранятся числа. Байт или ячейка памяти может хранить набор флагов (установлен — сброшен), представляющих собой информацию о состоянии чего-либо. С помощью битовых логических операций можно проверить, какие биты в байте установлены в единицу, можно обнулить биты или, наоборот, установить в единицу. Также существует возможность сменить значения битов на противоположные.
Проверка битов
Проверка битов осуществляется с помощью битовой логической операции and .
Представим, что имеется байт памяти с неизвестным нам содержимым. Известно, что логическая операция and возвращает 1, если только оба операнда содержат 1. Если к неизвестному числу применить побитовое логическое умножение (операцию and ) на число 255 (что в двоичном представлении 1111 1111), то в результате мы получим неизвестное число. Обнулятся те единицы двоичного представления числа 255, которые будут умножены на разряды неизвестного числа, содержащие 0. Например, пусть неизвестное число 38 (0010 0110), тогда проверка битов будет выглядеть так:
Другими словами, x and 255 = x .
Обнуление битов
Чтобы обнулить какой-либо бит числа, нужно его логически умножить на 0.
Обратим внимание на следующее:
1111 1110 = 254 = 255 - 1 = 255 - 20 1111 1101 = 253 = 255 - 2 = 255 - 21 1111 1011 = 251 = 255 - 4 = 255 - 22 1111 0111 = 247 = 255 - 8 = 255 - 23 1110 1111 = 239 = 255 - 16 = 255 - 24 1101 1111 = 223 = 255 - 32 = 255 - 25 1011 1111 = 191 = 255 - 64 = 255 - 26 0111 1111 = 127 = 255 - 128 = 255 - 27
Т.е. чтобы обнулить четвертый с конца бит числа x , надо его логически умножить на 247 или на (255 - 23).
Установка битов в единицу
Для установки битов в единицу используется побитовая логическая операция or . Если мы логически сложим двоичное представление числа x с 0000 0000, то получим само число х . Но вот если мы в каком-нибудь бите второго слагаемого напишем единицу, то в результате в этом бите будет стоять единица.
Отметим также, что:
0000 0001 = 20 = 1 0000 0010 = 21 = 2 0000 0100 = 22 = 4 0000 1000 = 23 = 8 0001 0000 = 24 = 16 0010 0000 = 25 = 32 0100 0000 = 26 = 64 1000 0000 = 27 = 128
Поэтому, например, чтобы установить второй по старшинству бит числа x в единицу, надо его логически сложить с 64 ( x or 64 ).
Смена значений битов
Для смены значений битов на противоположные используется битовая операция xor . Чтобы инвертировать определенный бит числа x , в такой же по разряду бит второго числа записывают единицу. Если же требуется инвертировать все биты числа x , то используют побитовую операцию исключающего ИЛИ ( xor ) с числом 255 (1111 1111).
Операции побитового циклического сдвига
Помимо побитовых логических операций во многих языках программирования предусмотрены битовые операции циклического сдвига влево или вправо. Например, в языке программирования Паскаль эти операции обозначаются shl (сдвиг влево) и shr (сдвиг вправо).
Первым операндом операций сдвига служит целое число, над которым выполняется операция. Во втором операнде указывается, на сколько позиций сдвигаются биты первого числа влево или вправо. Например, 105 shl 3 или 105 shr 4 . Число 105 в двоичном представлении имеет вид 0110 1001.
При сдвиге влево теряются старшие биты исходного числа, на их место становятся младшие. Освободившиеся младшие разряды заполняются нулями.
При сдвиге вправо теряются младшие биты исходного числа, на их место становятся старшие. Освободившиеся старшие разряды заполняются нулями, если исходное число было положительным.