Чему равен результат побитового сдвига 110 2

Чему равен результат побитового сдвига 110 2

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

Содержание

Побитовые логические операции

Ряд источников по языкам низкого уровня называет побитовые логические операции просто логическими [1] [2] , но в терминологии программирования на языках высокого уровня в названиях битовых операций присутствуют прилагательные битовый, побитовый (например: «побитовое логическое И», оно же «побитовое умножение»), поразрядный.

В некоторых языках программирования названия операторов, соответствующих логическим и побитовым логическим операциям, похожи. Кроме того, язык программирования может допускать неявное приведение числового типа к логическому и наоборот. В таких языках программирования необходимо внимательно следить за использованием логических и побитовых операций, перемешивание которых может привести к ошибкам. Например, в C++ результатом выражения «2 && 1» ( логическое И ) является булево значение true, а результатом выражения «2 & 1» ( побитовое И ) — целое значение .

Побитовое отрицание (NOT)

Побитовое отрицание (или побитовое НЕ , или дополнение) — это унарная операция, действие которой эквивалентно применению логического отрицания к каждому биту двоичного представления операнда. Другими словами, на той позиции, где в двоичном представлении операнда был 0, в результате будет 1, и, наоборот, где была 1, там будет 0. Например:

НЕ 01

Побитовое «И» (AND)

Побитовое «И» — это бинарная операция, действие которой эквивалентно применению логического «И» к каждой паре битов, которые стоят на одинаковых позициях в двоичных представлениях операндов. Другими словами, если оба соответствующих бита операндов равны 1, результирующий двоичный разряд равен 1; если же хотя бы один бит из пары равен 0, результирующий двоичный разряд равен 0.

И 0011
0101
0001

Побитовое «ИЛИ» (OR)

Побитовое «ИЛИ» — это бинарная операция, действие которой эквивалентно применению логического «ИЛИ» к каждой паре битов, которые стоят на одинаковых позициях в двоичных представлениях операндов. Другими словами, если оба соответствующих бита операндов равны 0, двоичный разряд результата равен 0; если же хотя бы один бит из пары равен 1, двоичный разряд результата равен 1.

ИЛИ 0011
0101
0111

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

Исключающее «ИЛИ» (или сложение по модулю 2) — это бинарная операция, результат действия которой равен 1, если число складываемых единичных битов нечётно, и равен 0, если чётно. Другими словами, если оба соответствующих бита операндов равны между собой, двоичный разряд результата равен 0; в противном случае, двоичный разряд результата равен 1.

Искл. ИЛИ 0011
0101
0110

Первое русское название операции обусловлено тем, что результат данной операции отличается от результата «ИЛИ» только в одном случае из 4 случаев входа — обоих 1 (случай одновременной истинности аргументов «исключается»). Ещё в русской грамматике значение данной логической связки передаётся союзом «либо».

Второе название — тем, что действительно является сложением в кольце вычетов по модулю два, из чего следуют некоторые интересные свойства. Например, в отличие от вышеописанных «И» и «ИЛИ», данная операция является обратимой, или инволютивной: ( x ⊕ y ) ⊕ y = x <displaystyle (xoplus y)oplus y=x> .

В компьютерной графике «сложение по модулю два» применяется при выводе спрайтов на картинку — повторное её применение убирает спрайт с картинки. Благодаря инволютивности эта же операция нашла применение в криптографии как простейшая реализация абсолютно стойкого шифра (шифра Вернама). «Сложение по модулю два» также может использоваться для обмена двух переменных, используя алгоритм обмена при помощи исключающего ИЛИ.

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

Другие побитовые логические операции

В распространённых языках программирования встроенными средствами реализуются только четыре побитовые логические операции: И, ИЛИ, НЕ и исключающее ИЛИ . Для задания произвольной побитовой логической операции вполне достаточно перечисленных, и, более того, как следует из теории булевых функций, можно ограничиться ещё меньшим набором базовых операций. Есть также языки программирования, где существует встроенная возможность выполнить любую бинарную логическую операцию побитово. Например, в PL/I есть встроенная функция BOOL, третий аргумент которой предназначен для указания произвольной логической операции, которую необходимо побитово применить к первым двум аргументам [3] .

Битовые сдвиги

К битовым операциям также относят битовые сдвиги. При сдвиге значения битов копируются в соседние по направлению сдвига. Различают несколько видов сдвигов — логический, арифметический и циклический, в зависимости от обработки крайних битов.

Также различают сдвиг влево (в направлении от младшего бита к старшему) и вправо (в направлении от старшего бита к младшему).

    Переводы, 11 марта 2016 в 0:37
Читайте также:  Exynos 7885 vs snapdragon 660

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

Введение

Побитовые операторы проводят операции непосредственно на битах числа, поэтому числа в примерах будут в двоичной системе счисления.

Я расскажу о следующих побитовых операторах:

  • | (Побитовое ИЛИ (OR)),
  • & (Побитовое И (AND)),
  • ^ (Исключающее ИЛИ (XOR)),

(Побитовое отрицание (NOT)),

  • > (Побитовый сдвиг вправо).
  • Битовые операции изучаются в дискретной математике, а также лежат в основе цифровой техники, так как на них основана логика работы логических вентилей — базовых элементов цифровых схем. В дискретной математике, как и в цифровой технике, для описания их работы используются таблицы истинности. Таблицы истинности, как мне кажется, значительно облегчают понимание битовых операций, поэтому я приведу их в этой статье. Их, тем не менее, почти не используют в объяснениях побитовых операторов высокоуровневых языков программирования.

    О битовых операторах вам также необходимо знать:

    1. Некоторые побитовые операторы похожи на операторы, с которыми вы наверняка знакомы (&&, ||). Это потому, что они на самом деле в чем-то похожи. Тем не менее, путать их ни в коем случае нельзя.
    2. Большинство битовых операций являются операциями составного присваивания.

    Побитовое ИЛИ (OR)

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

    38 | 53 будет таким:

    A 1 1 1
    B 1 1 1 1
    A | B 1 1 1 1 1

    В итоге мы получаем 1101112 , или 5510 .

    Побитовое И (AND)

    Побитовое И — это что-то вроде операции, противоположной побитовому ИЛИ. Двоичный разряд результата равен 1 только тогда, когда оба соответствующих бита операндов равны 1. Другими словами, можно сказать, двоичные разряды получившегося числа — это результат умножения соответствующих битов операнда: 1х1 = 1, 1х0 = 0. Побитовому И соответствует следующая таблица истинности:

    Пример работы побитового И на выражении 38 & 53:

    A 1 1 1
    B 1 1 1 1
    A & B 1 1

    Как результат, получаем 1001002 , или 3610 .

    С помощью побитового оператора И можно проверить, является ли число четным или нечетным. Для целых чисел, если младший бит равен 1, то число нечетное (основываясь на преобразовании двоичных чисел в десятичные). Зачем это нужно, если можно просто использовать %2 ? На моем компьютере, например, &1 выполняется на 66% быстрее. Довольно неплохое повышение производительности, скажу я вам.

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

    Разница между исключающим ИЛИ и побитовым ИЛИ в том, что для получения 1 только один бит в паре может быть 1:

    Например, выражение 138^43 будет равно…

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

    С помощью ^ можно поменять значения двух переменных (имеющих одинаковый тип данных) без использования временной переменной.

    Также с помощью исключающего ИЛИ можно зашифровать текст. Для этого нужно лишь итерировать через все символы, и ^ их с символом-ключом. Для более сложного шифра можно использовать строку символов:

    Исключающее ИЛИ не самый надежный способ шифровки, но его можно сделать частью шифровального алгоритма.

    Побитовое отрицание (NOT)

    Побитовое отрицание инвертирует все биты операнда. То есть, то что было 1 станет 0, и наоборот.

    Вот, например, операция

    A 1 1 1

    A

    1 1 1 1 1

    Результатом будет 20310

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

    Дополнительный код

    Здесь мне стоит рассказать вам немного о способе представления отрицательных целых чисел в ЭВМ, а именно о дополнительном коде (two’s complement). Не вдаваясь в подробности, он нужен для облегчения арифметики двоичных чисел.

    Главное, что вам нужно знать о числах, записанных в дополнительном коде — это то, что старший разряд является знаковым. Если он равен 0, то число положительное и совпадает с представлением этого числа в прямом коде, а если 1 — то оно отрицательное. То есть, 10111101 — отрицательное число, а 01000011 — положительное.

    Чтобы преобразовать отрицательное число в дополнительный код, нужно инвертировать все биты числа (то есть, по сути, использовать побитовое отрицание) и добавить к результату 1.

    Например, если мы имеем 109:

    A 1 1 1 1 1

    A

    1 1 1

    A+1

    1 1 1 1

    Представленным выше методом мы получаем -109 в дополнительном коде.
    Только что было представлено очень упрощенное объяснение дополнительного кода, и я настоятельно советую вам детальнее изучить эту тему.

    Побитовый сдвиг влево

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

    Читайте также:  Cube escape paradox 2 глава бесплатно
    A 1 1 1 1
    A N . Таким образом, 43 . Использование сдвига влево вместо Math.pow обеспечит неплохой прирост производительности.

    Побитовый сдвиг вправо

    Как вы могли догадаться, >> сдвигает биты операнда на обозначенное количество битов вправо.

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

    Так как побитовый сдвиг вправо — это операция, противоположная побитовому сдвигу влево, несложно догадаться, что сдвиг числа вправо на N количество позиций также делит это число на 2 N . Опять же, это выполняется намного быстрее обычного деления.

    Вывод

    Итак, теперь вы знаете больше о битовых операциях и не боитесь их. Могу предположить, что вы не будете использовать >>1 при каждом делении на 2. Тем не менее, битовые операции неплохо иметь в своем арсенале, и теперь вы сможете воспользоваться ими в случае надобности или же ответить на каверзный вопрос на собеседовании.

    Введение

    Я зык Си иногда называют макроассемблером за его тягу к железу. Если не использовать оптимизацию, можно даже примерно оценить, в какие конструкции на ассемблере преобразуется код программы. Простота и минимализм языка (простоту языка не путать с простотой программирования на языке) привели к тому, что на многих платформах си остаётся единственным высокоуровневым языком программирования. Без обзора побитовых операций, конечно, изучения языка было бы неполным.

    Побитовые операции, как понятно из названия, позволяют оперировать непосредственно с битами. Большое количество примеров использования побитовых операций можно найти, например, в книге Генри Уоррена «Алгоритмические трюки для программистов». Здесь мы рассмотрим только сами операции и примитивные алгоритмы.

    Побитовые И, ИЛИ, НЕ, исключающее ИЛИ

    ЗАМЕЧАНИЕ: здесь и далее в примерах используются 8-битные числа для упрощения записи. Всё это верно и для любых других чисел.

    Н апомню для начала, что логические операции И, ИЛИ, исключающее ИЛИ и НЕ могут быть описаны с помощью таблиц истинности

    Логический оператор И

    X Y X AND Y
    1
    1
    1 1 1
    Логический оператор ИЛИ

    X Y X OR Y
    1 1
    1 1
    1 1 1
    Логический оператор исключающее ИЛИ

    X Y X XOR Y
    1 1
    1 1
    1 1
    Логический оператор НЕ

    X NOT X
    1
    1

    В побитовых (bit-wise) операциях значение бита, равное 1, рассматривается как логическая истина, а 0 как ложь. Побитовое И (оператор &) берёт два числа и логически умножает соответствующие биты. Например, если логически умножить 3 на 8, то получим 0

    Так как в двоичном виде 3 в виде однобайтного целого представляет собой

    Первый бит переменной c равен логическому произведению первого бита числа a и первого бита числа b. И так для каждого бита.

    00000011
    00001000 ↓↓↓↓↓↓↓↓
    00000000

    Соответственно, побитовое произведение чисел 31 и 17 даст 17, так как 31 это 00011111 , а 17 это 00010001

    00011111
    00010001 ↓↓↓↓↓↓↓↓
    00010001

    Побитовое произведение чисел 35 и 15 равно 3.

    00100011
    00001111 ↓↓↓↓↓↓↓↓
    00000011

    Аналогично работает операция побитового ИЛИ (оператор |), за исключением того, что она логически суммирует соответствующие биты чисел без переноса.

    выведет 15, так как 15 это 00001111 , а 11 это 00001011

    00001111
    00001011 ↓↓↓↓↓↓↓↓
    00001111

    Побитовое ИЛИ для чисел 33 и 11 вернёт 43, так как 33 это 00100001 , а 11 это 00001011

    00100001
    00001011 ↓↓↓↓↓↓↓↓
    00101011

    Побитовое отрицание (оператор

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

    Выведет -66, так как 65 это 01000001 , а инверсия даст 10111110

    что равно -66. Кстати, вот алгоритм для того, чтобы сделать число отрицательным: для нахождение дополнительного кода числа его надо инвертировать и прибавить к нему единицу.

    Исключающее ИЛИ (оператор ^) применяет побитово операцию XOR. Например, для чисел

    будет выведено 89, так как a равно 00001100 , а b равно 01010101 . В итоге получим 01011001

    Иногда логические операторы && и || путают с операторами & и |. Такие ошибки могут существовать в коде достаточно долго, потому что такой код в ряде случаев будет работать. Например, для чисел 1 и 0. Но так как в си истиной является любое ненулевое значение, то побитовое умножение чисел 3 и 4 вернёт 0, хотя логическое умножение должно вернуть истину.

    Операции побитового сдвига

    О пераций сдвига две – битовый сдвиг влево (оператор >). Битовый сдвиг вправо сдвигает биты числа вправо, дописывая слева нули. Битовый сдвиг влево делает противоположное: сдвигает биты влево, дописывая справа нули. Вышедшие за пределы числа биты отбрасываются.

    Например, сдвиг числа 5 влево на 2 позиции

    Читайте также:  Типы спряжения глаголов в русском языке

    Сдвиг числа 19 вправо на 3 позиции

    00010011 >> 3 == 00000010

    Независимо от архитектуры (big-endian, или little-endian, или middle-endian) числа в двоичном виде представляются слева направо, от более значащего бита к менее значащему. Побитовый сдвиг принимает два операнда – число, над которым необходимо произвести сдвиг, и число бит, на которое необходимо произвести сдвиг.

    Так как сдвиг вправо (>>) дописывает слева нули, то для целых чисел операция равносильна целочисленному делению пополам, а сдвиг влево умножению на 2. Произвести битовый сдвиг для числа с плавающей точкой без явного приведения типа нельзя. Это вызвано тем, что для си не определено представление числа с плавающей точкой. Однако можно переместить число типа float в int, затем сдвинуть и вернуть обратно

    Но мы, конечно же, получим не 5.0f, а совершенно другое число.

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

    В данном случае при первом сдвиге всё работает, как и задумано, потому что число без знака. Во втором случае компилятор VSE2013 оставляет знак. Однако если посмотреть на представление этого числа, как беззнакового, сдвиг происходит по другим правилам, с сохранением самого левого бита. В последней строчке, если привести число со знаком к числу без знака, то произойдёт обычный сдвиг, и мы получим в результате положительное число.

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

    Примеры

    1. Напишем функции, которые позволяют определять и изменять определённый бит числа

    Для того, чтобы узнать, какой бит (1 или 0) стоит на позиции n, воспользуемся логическим умножением.

    Пусть имеется число 9

    Нужно узнать, выставлен ли бит на позиции 3 (начиная с нуля). Для этого умножим его на число, у которого все биты равны нулю, кроме третьего:

    00001001 & 00001000 = 00001000

    Теперь узнаем значение бита в позиции 6

    00001001 & 01000000 = 00000000

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

    Заметьте, что в функции условие записано так

    Потому что без скобок сначала будет вычислено равенство нулю и только потом выполнено умножение.

    Функцию можно упростить

    Функция, которая выставляет бит на n-й позиции в единицу.

    Известно, что логическое сложение любого бита с 1 будет равно 1. Так что для установки n-го бита нужно логически сложить число с таким, у которого все биты, кроме нужного, равны нулю. Как получить такое число, уже рассмотрено.

    Функция, которая устанавливает бит на n-й позиции в ноль.

    Для этого нужно, чтобы все биты числа, кроме n-го, не изменились. Умножим число на такое, у которого все биты равны единице, кроме бита под номером n. Например

    0001011 & 1110111 = 0000011

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

    Функция, изменющая значение n-го бита на противоположное.

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

    Битовые флаги

    Расммотрим синтетический пример. Пусть у нас есть три логические переменные, и нам нужно вывести определённое значение в зависимости от всех этих переменных сразу. Очевидно, что может быть 2 3 возможных вариантов. Запишем это условие в виде ветвления:

    Мы получили 8 ветвей. Пусть теперь нам понадобилось добавить ещё одно условие. Тогда число ветвей удвоится, и программа станет ещё сложней для понимания и отладки. Перепишем пример.

    Если каждое из наших логичесих значений сдвинуть на своё число бит влево и логически сложить, то мы получим свою уникальную комбинацию бит в зависимоти от значений a, b и c:

    Используем этот подход к нашей задаче и заменим ветвеление на switch:

    Этот метод очень часто используется для назначения опций функций в разных языках программирования. Каждый флаг принимает своё уникальное название, а их совместное значение как логическая сумма всех используемых флагов. Например, библиотека fcntl:

    Здесь флаг O_RDWR рaвен

    00000000000000000000001000000000

    и O_APPEND

    Ссылка на основную публикацию
    Чем открыть файл html на компьютере
    Автор: Юрий Белоусов · 21.11.2018 Каждый вебмастер знает, что такое HTML: это – язык гипертекстовой разметки, с помощью которой создается...
    Фотоаппарат сони dsc h50
    Название объектива : Carl Zeiss Vario-Tessar Количество групп оптических элементов : 8 Количество оптических элементов : 13 Цифровой Zoom :...
    Фотоаппараты до 10000 рублей рейтинг
    На российском рынке представлено настолько много фотоаппаратов и камер, что найдется модель на любой вкус. В том числе есть действительно...
    Чем открыть файл mtf тесты
    �������� (����.): ���� ����� MyTest �������� (���.): ���� ����� MyTest ��������: MTF ��� ���� ����� MyTest ������������ ����� ������ �����,...
    Adblock detector