Битовые операции

В С++ есть следующие битовые операции: & битовое и; | битовое или; ^ исключающее или; ~ дополнение; >> сдвиг вправо на указанное количество разрядов (бит); << сдвиг влево на указанное количество разрядов (бит). Первые три операции являются бинарными. Они работают с двоичным представлением двух операндов (констант, переменных или выражений). Они выполняются над каждой парой битов по тем же правилам, что и логические операции:

& | ^

1 1 1 1 0

1 0 0 1 1

0 1 0 1 1

0 0 0 0 0

Пример 1. Определить результат: short int k1=30,k2=-1707,r; r=k1 & k2;

cout<<endl<< k1<< “&”<<k2<<”=”<<r;

1. Представляем положительное число 30 в оперативной памяти. Для этого переводим его в двоичную систему счисления делением на 2 следующим образом: 30/2=15 (0 в остатке), 15/2=7 (1 в остатке), 7/2=3 (1), 3/2=1(1), 1/2=0(1). Записывая все остатки в обратном порядке, получим 30₁₀ =11110₂. Представляем это число в двух байтах, так как оно объявлено как short int. Для этого дописываем слева нули и получаем 0000000000011110.

2. Представляем отрицательное число –1707 в оперативной памяти в дополнительном коде. Для этого выполняем следующее:

2.1) так как делением на 2 перевод в двоичную систему счисления выполняется долго, сначала переведём число 1707 во вспомогательную шестнадцатеричную систему счисления делением на 16. 1707/16=106 (11 в остатке), 106/16=6 (10), 6/16=0(6). Записывая все остатки в шестнадцатеричной системе счисления в обратном порядке, получим 6AB₁₆, так как 10₁₀=A₁₆, 11₁₀=B₁₆;

2.2) каждую шестнадцатеричную цифру полученного результата записываем в виде четырёх двоичных цифр (двоичной тетрады): 011010101011;

2.3) представляем это число в двух байтах, так как оно объявлено как short int. Для этого дописываем слева необходимое количество нулей: 0000011010101011. Получили представление положительного числа в памяти компьютера;

2.4) для получения дополнительного кода выполняем инверсию положительного представления с учётом “левых” нулей, т. е. нуль меняем на единицу, единицу на нуль. К результату инверсии прибавляем единицу. Получим 1111100101010101.

3. К полученным таким образом двоичным кодам двух чисел применяем битовую операцию и (&). При этом единицы получаем только там, где были обе единицы, во всех остальных разрядах получатся нули: 0000000000010100.

4. Что это за число в десятичной системе счисления? Разбиваем его на тетрады и получаем число в шестнадцатеричной системе счисления: 14₁₆. Для перевода в десятичную систему счисления записываем его как сумму степеней числа 16, умноженную на соответствующую шестнадцатеричную цифру: 14₁₆=1*16+4=20₁₀. При этом действия выполняются в десятичной системе счисления.

Пример 2. Найти r2=30| -1707, если a) short r2, b) unsigned short r2.

По умолчанию подразумевается тип int. К полученным в предыдущем упражнении двоичным кодам применяем битовую операцию или (|). При этом нули получаются только там, где были оба нуля, во всех остальных разрядах получатся единицы: 1111100101011111.

a) Так как результат объявлен как знаковое число (по умолчанию signed) и в самом левом бите получилась единица, то это дополнительный код отрицательного числа. Для его получения выполняем в обратном порядке то, что делали в пункте 2) предыдущего упражнения: вычитаем единицу и выполняем инверсию. Получим 0000011010100001. Разбив на тетрады, получаем 6A1₁₆=6*16²+10*16+1=1697. Ответ: –1697.

b) Так как при таком объявлении (unsigned) отрицательного числа быть не может, то мы имеем положительное число, несмотря на единицу в самом левом бите. Разбиваем двоичное число на тетрады и переводим его в десятичную систему счисления F95F₁₆=15*16³+9*16²+5*16+15=63839.

Пример 3. Пусть short r3. Определить результат: r3=~30.

Операция дополнение (~) меняет единицу на нуль, а нуль на единицу. Поэтому к полученному в упражнении 1 двоичному коду числа 30 0000000000011110 применяем инверсию: 1111111111100001. Так как по умолчанию переменная имеет модификатор signed и в самом левом бите получена единица, то это отрицательное число. Для его восстановления вычитаем единицу и выполняем инверсию: 0000000000011111=1F₁₆=1*16+15=31.

Операция << (сдвиг влево) имеет общий вид a<<m, где a — число, участвующее в сдвиге, а m показывает, на какое количество разрядов сдвигаем число. При этом как для положительных, так и для отрицательных чисел “вращение”, или циклический сдвиг, не выполняется. Значения левых сдвинутых бит теряются, а справа появляются нули.

Пример 4. char k= –5; for(int I=1; I<=4; I++)

{ k<<=1; // или k=k<<1;

printf("%5d",k); }

Получим –10, –20, –40, –80. Почему? Число –5 имеет следующее представление в одном байте (тип char): 11111011. После сдвига на один разряд имеем 11110110. При этом левая крайняя единица потерялась, и справа появилось число 0, а не 1. Так как это отрицательное число, то после вычитания единицы и инверсии получаем 00001010, т. е. число -10. Аналогично получаем остальные числа.

Сдвиг влево на один разряд означает увеличение целого числа в два раза, сдвиг влево на два разряда увеличивает число в четыре раза и так далее, сдвиг влево на m разрядов равносилен увеличению числа в 2^m раза. Это не зависит от того, какое число, положительное или отрицательное, участвовало в сдвиге.

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

Сдвиг вправо на один разряд означает целочисленное деление на 2, сдвиг вправо на два разряда означает целочисленное деление на 4 и так далее, сдвиг вправо на m разрядов равносилен целочисленному делению числа на 2^m

Пример 5. a) 42>>2 даёт 10₁₀. Действительно, 42=00101010₂, а в результате сдвига получаем 00001010₂=10₁₀.

b) В результате операции –42>>2 получим –11. Почему? –42=11010110₂, а после сдвига получим 11110101₂, а это отрицательное число–11.

В качестве упражнения выполните следующий фрагмент программы и объясните результат:

char k= –30; cout<<endl;

for(int I=1; I<=4; I++) { k>>=1; // или k=k>>1;

printf ("%5d", k); }