Как я учился программировать на языке С++ >> Глава 1 >> Раздел 10

Раздел 10

Побитовые операторы и двоичное представление чисел

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

Как известно, целые числа представляются в виде последовательности цифр. Такое представление чисел называется позиционным. Весь набор цифр, которые могут использоваться в позиционном представлении числа, определяют систему счисления. В повседневной жизни используется десятичная система счисления, в которой числа представлены цифрами от 0 до 9.

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

Каждая позиция в двоичном представлении числа соответствует биту. Таким образом, с помощью бита можно записать два значения: 0 или 1. Если для представления числа используется n бит, то в этом случае существует 2ⁿ различных комбинаций, каждая из которых соответствует отдельному числу. Например, с помощью 8 бит(1 байт) можно записать 2⁸ = 256 чисел.

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

Для определения знака числа используют старший бит в позиционной записи. Нулевой старший бит соответствует положительному числу, а единичный старший бит соответствует отрицательному числу. При этом перевод для положительных чисел из двоичной системы счисления в десятичную осуществляется стандартными методами: если в двоичном представлении число позиционно задается как b_nb_n-1...b₂b₁b₀ (причем цифры b_i могут принимать значения 0 или 1, а старший бит для положительных чисел равен 0), то в десятичной системе число вычисляется как b₀2⁰ + b₁2¹ + b₂2² + ... + b_n-12^n-1 + b_n2ⁿ.

С отрицательными числами дела обстоят несколько сложнее. Чтобы перевести отрицательное число с позиционным представлением в двоичной системе b_nb_n-1...b₂b₁b₀ (старший бит для отрицательного числа b_n = 1), необходимо проделать несложную процедуру из двух этапов.

Во-первых, производится побитовое инвертирование кода, т.е.  каждый бит в представлении числа меняется на противоположный: 0 на 1 и 1 на 0.

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

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

Проиллюстрируем это не примере.

Рассмотрим 8-битовое бинарное положительное число 01001011, что в десятичной системе счисления соответствует числу 2⁰ + 2¹ + 2³ + 2⁶ = 1 + 2 + 8 + 64  = 75.

Определим бинарное машинное представление для отрицательного числа -75. Отнимем от модуля числа единицу, получаем 74. Бинарное представление для этого числа 01001010 (74 = 2¹ + 2³ + 2⁶). После побитового инвертирования из числа 01001010 получаем 10110101. Это и есть представление числа -75.

В том, что это так, легко убедиться: сложим числа 01001010 и 10110101. Формально получаем 100000000, однако поскольку числа 8-битовые, лишний единичный старший бит отбрасывается, и получается представление 00000000, что соответствует нулю, как и должно быть.

Теперь рассмотрим основные побитовые операции и операторы, которые используются для этого в языке программирования С++. Список побитовых операторов приведен в таблице 1.6.

Таблица 1.6 Побитовые операторы С++
Оператор	Назначение
&	Побитовое И. Бинарный оператор. Результатом выражения a&b является число, каждый бит которого в двоичном представлении равен результату сравнения соответствующих битов a и b: значение равно 1, если оба сравниваемых бита равны 1. В противном случае значение бита равно 0.
|	Побитовое ИЛИ. Бинарный оператор. Результатом выражения a | b является число, каждый бит которого в двоичном представлении равен результату сравнения соответствующих битов чисел a и b: значение бита равно 1, если хотя бы один из сравниваемых битов равен 1. В противном случае значение бита равно 0.
^	Побитовое исключающее ИЛИ. Бинарный оператор. Результатом выражения a ^ b является число, каждый бит которого в двоичном представлении равен результату сравнения соответствующих битов чисел a и b: значение бита равно 1, если один и только один из сравниваемых битов равен 1. В противном случае значение бита равно 0.
~	Побитовое отрицание(дополнение до единицы). Унарный оператор. Результатом выражения ~a является число, которое получается побитовым инвертированием числа а.
>>	Сдвиг вправо. Бинарный оператор. В двоичном представлении числа, указанном слева от оператора, выполняется сдвиг всех битов вправо на число позиций, указанных справа от оператора. При этом старший бит знака остается неизменным, а выходящие за диапазон младшие биты теряются.
<<	Сдвиг влево. Бинарный оператор. В двоичном представлении числа, указанном слева от оператора, выполняется сдвиг всех битов влево на число позиций, указанных справа от оператора, с заполнением младших битов нулями и потерей старших битов.

Приведем некоторые примеры использования побитовых операторов. Они представлены в таблице 1.7. Даже в самых простых случаях результат может оказаться весьма неожиданным.

Таблица 1.7 Примеры использования побитовых операторов
Выражение	Значение	Пояснение
5 & 3	1	В двоичном представлении число 5 имеет вид 101, а число 3 представляется как 011. Побитовое сравнение чисел 101 и 011 с помощью побитового И & дает 001, что в десятичной системе соответствует числу 1.
5 | 3	7	Применение оператора побитового ИЛИ |  для сравнения чисел 101 и 011 дает 111, что в десятичной системе соответствует числу 7.
5 ^ 3	6	Применение оператора побитового исключающего ИЛИ ^  для сравнения чисел 101 и 011 дает 110, что в десятичной системе соответствует числу 6.
~5	-6	После применения операции побитового инвертирования ~ к числу 5 требует особых пояснений. На самом деле в 8-битовом представлении число 5 имеет вид 00000101. В предыдущих случаях нулевые старшие разряды роли не играли, поэтому они явно не указывались. При инвертировании наличие старших нулевых битов важно. Инвертирование дает 11111010. Это не что иное, как представление  в двоичном машинном коде числа -6. Последнее читатель может проверить самостоятельно.
5 >> 2	1	После сдвига вправо на две позиции для числа 5(двоичный код 101) получаем 001. В десятичной системе это число 1.
5 << 2	20	После сдвига влево на две позиции для числа 5(двоичный код 101) получаем 00100. В десятичной системе это число 20.

Обращаем внимание читателя  на особенности применения операции побитового сдвига к отрицательным числам. Например, результатом выражения -6 >> 5 является число -1. Дело в том, что в бинарном коде 11111010 для числа -6  при сдвиге вправо на 5 позиций при условии сохранения значения ставшего бита знака получаем  код 11111111. Это код числа -1.

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

Представим, что число задается 8 битами.

Если воспользоваться командной 1 << 6,  получим в качестве результата значение 2⁶=64.

Действительно, десятичное число 1 в двоичной системе в 8-битовом представлении задается как 00000001. после сдвига влево на 6 позиций получаем 01000000, что в десятичной системе соответствует числу 64.

Однако если воспользоваться командой 1 << 7, получим в качестве результата  -128.

Объясняется это следующим обстоятельством

После сдвига влево на 7 позиций из числа 00000001, получаем число 10000000.

Это отрицательное число, о чем свидетельствует старший единичный бит.

Переводя это число в десятичную систему, сначала инвертируем бинарный код и получаем 01111111. Это код числа 127. Чтобы получить конечное значение, необходимо прибавить к этому результату 1 и добавить минус - в результате приходим к значению -128.