Так как на уровне схем почти вся логика бинарная, ровно такое представление и используется для хранения чисел в компьютерах: каждая целочисленная переменная указывает на какую-то ячейку из 8 ( char ), 16 ( short ), 32 ( int ) или 64 ( long long ) бит.
Эндианность
Единственная неоднозначность в таком формате возникает с порядком хранения битов — также называемый эндианностью. Зависимости от архитектуры он может быть разным:
Хотя big-endian более естественный для понимания — на бумаге мы ровно так обычно и записываем бинарные числа — по разным причинам на большинстве современных процессоров по умолчанию используется little endian.
Иными словами, «$i$-тый бит» означает «$i$-тый младший» или «$i$-тый справа», но на бумаге мы ничего не инвертируем и записываем двоичные числа стандартным образом.
Битовые операции
Помимо арифметических операций, с числами можно делать и битовые, которые интерпретируют их просто как последовательность битов.
Сдвиги
Битовую запись числа можно «сдвигать» влево ( x ) или вправо ( x >> y ), что эквивалентно умножению или делению на степень двойки с округлением вниз.
Обычное умножение и деление — не самые быстрые операции, однако все битовые сдвиги всегда работают ровно за один такт. Как следствие, умножение и деление на какую-то фиксированную степень двойки всегда работает быстро — даже если вы не используете сдвиги явно, компилятор скорее всего будет проводить подобную оптимизацию.
Побитовые операции
Все побитовые операции тоже работают за один такт, вне зависимости от типа данных. Для больших не вмещающихся в один регистр битовых последовательностей существует битсет.
Маски
Битовые операции таким образом часто используются операций над множествами, представляемыми битовыми мазками — например, в задачах на полный перебор или динамическое программирование.
Выделить i-й бит числа
Напомним, что нумерация идет с младших бит и начинается с нуля.
Получить число, состоящее из k единиц
Инвертировать все биты числа
Добавить i-й элемент в множество
Удалить i-й элемент из множества, если он есть
Также добавляет этот элемент, если его нет.
Знаковые числа
Целочисленные переменные делятся на два типа — знаковые (signed) и беззнаковые (unsigned).
Упражнение. Каких чисел больше: положительных или отрицательных?
Осторожно. В стандарте C/C++ прописано, что переполнение знаковых переменных приводит к undefined behavior, поэтому полагаться на описанную логику переполнения нельзя, хотя равно это скорее всего и произойдет.
128-битные числа
Общих регистров размера больше 64 в процессорах нет, однако умножение и несколько смежных инструкций могут использовать два последовательных регистра как один большой. Это позволяет быстро перемножать два 64-битных числа и получать 128-битный результат, разделенный на нижние биты и верхние.
Это весьма специфичная операция, и поэтому в языках программирования нет полноценной поддержки 128-битных переменных. В C++ однако есть «костыль» — тип __int128_t — который фактически просто оборачивает пару из двух 64-битных регистров и поддерживает арифметические операции с ними.
Базовые арифметические операции с ним чуть медленнее, его нельзя напрямую печатать, и деление и прочие сложные операции будут вызывать отдельную библиотеку и поэтому работать очень долго, однако в некоторых ситуациях он оказывается очень полезен.
Побитовые операторы и двоичное представление чисел
Язык программирования С++ обладает полным набором побитовых операторов. Побитовые операторы применяются при выполнении операций с битами в двоичном представлении числовых значений. Прежде чем непосредственно рассмотреть сами операторы, кратко остановимся на концепции двоичного представления числовых значений.
Как известно, целые числа представляются в виде последовательности цифр. Такое представление чисел называется позиционным. Весь набор цифр, которые могут использоваться в позиционном представлении числа, определяют систему счисления. В повседневной жизни используется десятичная система счисления, в которой числа представлены цифрами от 0 до 9.
Каждая позиция в двоичном представлении числа соответствует биту. Таким образом, с помощью бита можно записать два значения: 0 или 1. Если для представления числа используется n бит, то в этом случае существует 2 n различных комбинаций, каждая из которых соответствует отдельному числу. Например, с помощью 8 бит(1 байт) можно записать 2 8 = 256 чисел.
С отрицательными числами дела обстоят несколько сложнее. Чтобы перевести отрицательное число с позиционным представлением в двоичной системе bnbn-1. b2b1b0 (старший бит для отрицательного числа bn = 1), необходимо проделать несложную процедуру из двух этапов.
Во-первых, производится побитовое инвертирование кода, т.е. каждый бит в представлении числа меняется на противоположный: 0 на 1 и 1 на 0.
Чтобы перевести число из десятичной системы в двоичную, проделывают обратную процедуру: от модуля отрицательного числа отнимается 1, результат переводится в бинарный код, после чего проводится побитовое инвертирование.
Проиллюстрируем это не примере.
Рассмотрим 8-битовое бинарное положительное число 01001011, что в десятичной системе счисления соответствует числу 2 0 + 2 1 + 2 3 + 2 6 = 1 + 2 + 8 + 64 = 75.
В том, что это так, легко убедиться: сложим числа 01001010 и 10110101. Формально получаем 100000000, однако поскольку числа 8-битовые, лишний единичный старший бит отбрасывается, и получается представление 00000000, что соответствует нулю, как и должно быть.
Теперь рассмотрим основные побитовые операции и операторы, которые используются для этого в языке программирования С++. Список побитовых операторов приведен в таблице 1.6.
Таблица 1.6 Побитовые операторы С++
Оператор
Назначение
&
a является число, которое получается побитовым инвертированием числа а.
Особенности операций в двоичной системе таковы, что сдвиг в побитовом представлении числа на одну позицию влево означает умножение этого числа на 2. Следует только помнить, что с определенного момента при сдвиге вправо теряются старшие биты.
Представим, что число задается 8 битами.
Если воспользоваться командной 1 6 =64.
Действительно, десятичное число 1 в двоичной системе в 8-битовом представлении задается как 00000001. после сдвига влево на 6 позиций получаем 01000000, что в десятичной системе соответствует числу 64.
Однако если воспользоваться командой 1 | Печать страницы | На основе Google Сайтов
Я зык Си иногда называют макроассемблером за его тягу к железу. Если не использовать оптимизацию, можно даже примерно оценить, в какие конструкции на ассемблере преобразуется код программы. Простота и минимализм языка (простоту языка не путать с простотой программирования на языке) привели к тому, что на многих платформах си остаётся единственным высокоуровневым языком программирования. Без обзора побитовых операций, конечно, изучения языка было бы неполным.
Побитовые операции, как понятно из названия, позволяют оперировать непосредственно с битами. Большое количество примеров использования побитовых операций можно найти, например, в книге Генри Уоррена «Алгоритмические трюки для программистов». Здесь мы рассмотрим только сами операции и примитивные алгоритмы.
Побитовые И, ИЛИ, НЕ, исключающее ИЛИ
ЗАМЕЧАНИЕ: здесь и далее в примерах используются 8-битные числа для упрощения записи. Всё это верно и для любых других чисел.
Н апомню для начала, что логические операции И, ИЛИ, исключающее ИЛИ и НЕ могут быть описаны с помощью таблиц истинности
Логический оператор ИЛИ
X
Y
X OR Y
0
0
0
0
1
1
1
0
1
1
1
1
Логический оператор исключающее ИЛИ
X
Y
X XOR Y
0
0
0
0
1
1
1
0
1
1
1
0
В побитовых (bit-wise) операциях значение бита, равное 1, рассматривается как логическая истина, а 0 как ложь. Побитовое И (оператор &) берёт два числа и логически умножает соответствующие биты. Например, если логически умножить 3 на 8, то получим 0
Так как в двоичном виде 3 в виде однобайтного целого представляет собой
Первый бит переменной c равен логическому произведению первого бита числа a и первого бита числа b. И так для каждого бита.
00000011 00001000 ↓↓↓↓↓↓↓↓ 00000000
00011111 00010001 ↓↓↓↓↓↓↓↓ 00010001
Побитовое произведение чисел 35 и 15 равно 3.
00100011 00001111 ↓↓↓↓↓↓↓↓ 00000011
Аналогично работает операция побитового ИЛИ (оператор |), за исключением того, что она логически суммирует соответствующие биты чисел без переноса.
00001111 00001011 ↓↓↓↓↓↓↓↓ 00001111
00100001 00001011 ↓↓↓↓↓↓↓↓ 00101011
Побитовое отрицание (оператор
) работает не для отдельного бита, а для всего числа целиком. Оператор инверсии меняет ложь на истину, а истину на ложь, для каждого бита. Например,
Исключающее ИЛИ (оператор ^) применяет побитово операцию XOR. Например, для чисел
Иногда логические операторы && и || путают с операторами & и |. Такие ошибки могут существовать в коде достаточно долго, потому что такой код в ряде случаев будет работать. Например, для чисел 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:
В языках C/C++ для хранения целых чисел выделяется фиксированный размер памяти (в отличии от, например, языка Python, где целые числа имеют произвольную длину, ограниченную только возможностями компьютера). Например, если для хранения целочисленной переменной выделено 4 байта (32 бита), то эта переменная может принимать \(2^<32>\) различных значений. В таких языках программирования, как C/C++ или Pascal бывают два вида целочисленных типов данных — знаковые и беззнаковые типы. В беззнаковом типе данных хранятся только неотрицательные значения. Минимальное беззнаковое значение, которое можно сохранить в такой переменной, записывается нулевыми битами и соответствует числу 0. Максимальное значение, которое можно записать в такой переменной, кодируется одними единицами и для 32-битной переменной равно \(2^<32>-1\). Далее в таблице приведены названия различных беззнаковых целых типов для различных языков программирования.
unsigned int, unsigned long
unsigned long long
unsigned long, unsigned long long
Представление знаковых целых чисел (дополнительный код)
Также можно заметить, что для преставления отрицательного числа \(-n\) необходимо взять двоичное представление числа \(n\), уменьшить его на 1, затем инвертировать все биты числа (заменить значение 0 на 1 и заменить 1 на 0). Такая операция также назыается дополнением, поэтому и код называется дополнительным.
Данный урок курса можно считать факультативным, т. е. необязательным. Для освоения темы этого урока вам потребуется знание о двоичной системе счисления, навыки перевода чисел из одной системы счисления в другую, а также вы должны иметь представление о том, что такое битовые (они же поразрядные) операции. С последним можно познакомиться по вот этой лекции.
В языке программирования C существуют следующие поразрядные операции: & (И), | (ИЛИ), ^ (исключающее ИЛИ), > (сдвиг вправо),
(поразрядное дополнение до единицы). Рассмотрим на примерах, как они работают, но перед этим уделим внимание выводу в языке C чисел в отличных от десятичной системах счисления.
В С можно присваивать целочисленные значения в десятичной, восьмеричной и шестнадцатеричной системах счисления. Для того, чтобы присвоить переменной число в восьмеричной системе счисления, перед ним надо написать 0 (ноль), в шестнадцатеричной — 0x (ноль и икс), например:
Любые целые числа можно выводить на экран в десятичном, восьмеричном и шестнадцатеричном представлении. Пример кода для вывода определенных ранее двух переменных в различных системаъ счисления:
В результате на экране вы увидите:
Восьмеричные и шестнадцатеричные числа используются из-за удобства при работе с двоичной системой счисления. Каждая цифра восьмеричного числа может быть заменена тремя цифрами двоичного. И каждая цифра шестнадцатеричного числа легко заменяет четыре разряда двоичного числа. Вот таблица соответствия цифр восьмеричной системы счисления числам двоичной системы:
0
000
1
001
2
010
3
011
4
100
5
101
6
110
7
111
Теперь допустим, что у нас есть восьмеричное число 037. По таблице легко понять, что в двоичном выражении оно будет выглядеть как 011 111.
Итак, если бы мы при работе с поразрядными операциями использовали десятичные числа, то чтобы оценить результат нам бы каждый раз приходилось переводить десятичное число в двоичную систему счисления, что относительно трудоемко. Если же человек видит, например, восьмеричное число, то он может представить как оно выглядит в двоичном представлении, помня или держа перед глазами таблицу соответствия чисел. Например, как только мы видим 017, то можем представить в уме, как последние четыре бита ячейки памяти забиты единицами.
Теперь вернемся к поразрядным операциям и протестируем каждую из них. Для этого напишем небольшую программу:
Результат ее работы будет выглядеть так:
Этот результат будет проще понять с помощью рисунка:
В последнем случае получилось такое большое число потому, что под форматы вывода целых чисел ( %d, %o, %X ) выделяется по 4 байта.
Вроде бы все просто, но как установить в единицу определенный бит числа? Существует закономерность соответствия степеней двойки и двоичного представления числа: 2 0 = 0000 0001 2 1 = 0000 0010 2 2 = 0000 0100 2 3 = 0000 1000 2 4 = 0001 0000 и т.д. Теперь если применить к mask побитовую операцию | (ИЛИ), а в качестве второго операнда использовать определенную степень двойки, то один бит будет установлен в 1. Например: (0) 0000 0000 | (2 5 ) 0010 0000 = 0010 0000 (32) 0010 0000 | (2 7 ) 1000 0000 = 1010 0000