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

Люди делятся на 10 типов – тех, кто знает двоичную систему и тех, кто не знает

И (&&) — логическая конъюнкция (умножение). Возвращает истину только в том случае, когда истинны два простых условия, находящиеся по бокам от нее.

Или (||) — логическая дизъюнкция (сложение). Внешнее условие будет истинно в том случае, когда хотя бы одно из внутренних условий верно.

не (!) — логическая инверсия (отрицание). Возвращает истину тогда, когда выполняется условие с частицей не.

Битовые операции в программировании выполняются над битами величин в их двоичном представлении.Битовых операций всего 6:

Оператор	Название	Значение
~a	побитовое отрицание (инверсия)	каждый бит a меняет свое значение на противоположное: 0 заменяется 1, 1-нулем
a & b	побитовое умножение (битовое И)	поочередно выполняет операцию И с соответствующими битами a и b
a | b	побитовое сложение (битовое ИЛИ)	поочередно выполняет операцию ИЛИ с соответствующими битами a и b
a ^ b	побитовое исключающее ИЛИ (XOR)	поочередно выполняет операцию ИСКЛЮЧАЮЩЕЕ ИЛИ (сложение по модулю 2) с соответствующими битами a и b
a << p	побитовый сдвиг влево	сдвигает все биты двоичной записи a влево на pбит
a >> p	побитовый сдвиг вправо	сдвигает все биты двоичной записи a вправо на pбит

Проиллюстрируем применение побитовых операций с помощью следующего кода (однобайтный беззнаковый тип unsigned char используем для наиболее краткой записи двоичной формы величин):

#include <iostream>

int main(){

unsigned char x = 49; // x = 00110001

unsigned char y = 103; // y = 01100111

unsigned char z = ~y; // z = 10011000 (z=152)

y = x & y;       // y = 00100001 (y=33)

z = z | y;       // z = 10111001 (z=185)

x = x ^ z;       // x = 10001000 (x=136)

x = x >> 2;      // x = 00100010 (x=34)

y = y << 1;      // y = 01000010 (y=66)

std::cout << (int)x << ' ' << (int)y << ' ' << (int)z << '\n';

return 0;

}

Для битовых операций допускается сокращенная форма записи, как и для арифметических. Т.е. вместо z = z | y можно было использовать z | = y, вместо x = x >> 2 записать x >>=2 и т.д. Развернутая форма записи в примере применялась для облегчения понимания побитовых операторов.

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

Стоит отметить, что операции побитового сдвига на p бит для беззнаковых целых типов эквивалентны умножению на 2^p (сдвиг влево) и делению нацело на 2^p (сдвиг вправо).

В самом деле, если, к примеру, умножить 33 (в двоичной форме 10001) на 2²=4 (в двоичной форме 100)

100001

×100

10000100

или 132 и т.д.

Например, если требуется определить значение наименьшего целого числа (можно это сделать также с помощью макроса MIN_ INT, который определён в заголовочном файле climits)

int imin = 1 << (sizeof(int) * 8 - 1);

cout << imin;

Также интересно, что рассматриваемую ранее задачу «Обмен без третьего» можно решить с использованием XOR(исключающее ИЛИ) для переменных одинаковой длины:

x = x ^ y;

y = y ^ x;

x = x ^ y;

или, в более краткой форме:

x ^= y ^= x ^= y;

ВАЖНО: Вообще говоря, битовые операции работают быстрее арифметических, однако современные компиляторы C++ производят качественную оптимизацию кода там, где это возможно. Поэтому не гоняйтесь без крайней необходимости за иллюзорным выигрышем в доли микросекунд, рискуя при неосторожном использовании битовых операций получить вполне реальную ошибку. Это ни к чему хорошему не приведет.

Задача №19. Коды Хэмминга (7;4)

Простейший пример кода, способного обнаруживать ошибки в себе, был предложен Ричардом Хэммингом и по его имени назван кодом Хэмминга (7; 4).  Для каждого набора из 4 бит A, B, C, D рассчитываются по 3 контрольных разряда. Разряды E, F и G называются контрольными. Они вычисляются по формулам:

       E = B Å A Å D

       F = B Å A Å C

       G = C Å A Å D

На рисунках разряды с исходными битами расположены в пересечениях кругов, а в остальной части вычисляются контрольные разряды как сумма по модулю 2 исходных битов в этом круге. 7-битовые наборы, построенные таким образом, называются правильными. Попробуйте изменить любой бит в правильном наборе и убедитесь, что всегда обнаруживается ошибка и можно восстановить исходный.

Например, для исходного сообщения ABCD = 1101 код Хэмминга (7; 4) может быть построен таким образом

Самокорректирующийся код Хэмминга может использоваться для исправления не более одной ошибки в сообщении.

Входные данные

Вы получаете сообщение из 7 бит, разделенных пробелами. Первые 4 бита являются информационными, а следующие 3 - контрольными, которые вычисляются по формулам из условия задачи.

Выходные данные

Выведите то же сообщение без пробелов, исправив ошибку, если она в нём была.

Решение

Очевидно, что разряд A влияет на все три контрольных разряда. Инверсия в бите A приведёт к тому, что расчётные разряды E, F, G для кода Хэмминга не совпадут с реальными значениями.

Аналогично B влияет на E и F, C на F и G, D на E и G. Если ошибка была допущена в контрольном разряде, то не совпадёт значение только в нём самом.

Т.е. инвертировать нужно биты, для которых происходит несовпадение значениё контрольных разрядов.

Очевидно, что сложение по модулю 2 с единицей эквивалентно инверсии бита. В самом деле

0 Å 1 = 1

1 Å 1 = 1

#include <iostream>

int main(){

short a, b, c, d, e, f, g, e1, f1, g1;

std::cin >> a >> b >> c >> d >> e >> f >> g;

e1 = b ^ a ^ d;

f1 = b ^ a ^ c;

g1 = c ^ a ^ d;

a ^= e1 != e && f1 != f && g1 != g;

b ^= e1 != e && f1 != f && g1 == g;

c ^= e1 == e && f1 != f && g1 != g;

d ^= e1 != e && f1 == f && g1 != g;

e ^= e1 != e && f1 == f && g1 == g;

f ^= e1 == e && f1 != f && g1 == g;

g ^= e1 == e && f1 == f && g1 != g;

std::cout << a << b << c << d << e << f;

}

Задача №20. День программиста (acmp.ru)

День программиста отмечается в 255-й день года (при этом 1 января считается нулевым днем). Требуется написать программу, которая определит дату (месяц и число григорианского календаря), на которую приходится День программиста в заданном году.

В григорианском календаре високосным является:

· год, номер которого делится нацело на 400

· год, номер которого делится на 4, но не делится на 100

Входные данные

В единственной строке входного файла INPUT.TXT записано целое число от 1 до 9999 включительно, которое обозначает номер года нашей эры.

Выходные данные

Вывести дату Дня программиста в формате DD/MM/YYYY, где DD — число, MM — номер месяца (01 — январь, 02 — февраль, ..., 12 — декабрь), YYYY — год в десятичной записи.

Примеры

№	Ввод	Вывод
1	2000	12/09/2000
2	2009	13/09/2009

Решение

Номер дня будет 12 для високосных годов и 13 для обычных. Номер месяца всегда 9. Для вывода года в требуемом формате воспользуемся флагами вывода setw– количество символов (4) и setfill– задаёт символ-заполнитель (0)

#include <iostream>

#include <iomanip>

#define DIV(p) (year % p == 0)

using namespace std;

int main() {

int year;

cin >> year;

bool leap = DIV(400) || (DIV(4) && !DIV(100));

cout << 13 - leap << "/09/" << setw(4) << setfill('0') << year;

}

Задача №21. Шахматная задача

«— Шахматы! — говорил Остап. — Знаете ли вы, что такое шахматы? Они двигают вперед не только культуру, но и экономику! Знаете ли вы, что ваш «Шахклуб четырех коней» при правильной постановке дела сможет совершенно преобразить город Васюки?

Остап со вчерашнего дня еще ничего не ел. Поэтому красноречие его было необыкновенно». (с) Ильф и Петров. 12 стульев

В альтернативной Вселенной в городе Нью-Москоу (бывшие Васюки, Москва переименована в Старые Васюки) готовится межпланетный шахматный турнир. Отличие шахмат альтернативной Вселенной состоит в том, что доска для игры в шахматы является неограниченной (см. рис. 11), а координаты каждой клетки задаются в виде пары чисел (x,y). В остальном отличий не имеется. Определите, сколько из шахматных фигур (ладья, слон, ферзь, король, конь) смогут сделать ход из клетки (x1,y1) в клетку (x2,y2).

Входные данные

Через пробел 4 целых числа x1, y1, x2, y2. Все числа по модулю не превышают 10⁹

Выходные данные

Одно число от 0 до 5 – искомое количество фигур.

Решение

… … … … … … … … … … -2,-2 -1,-2 0,-2 1,-2 2,-2 3,-2 4,-2 … … -2,-1 -1,-1 0,-1 1,-1 2,-1 3,-1 4,-1 … … -2,0 -1,0 0,0 1,0 2,0 3,0 4,0 … … -2,1 -1,1 0,1 1,1 2,1 3,1 4,1 … … -2,2 -1,2 0,2 1,2 2,2 3,2 4,2 … … -2,3 -1,3 0,3 1,3 2,3 3,3 4,3 … … -2,4 -1,4 0,4 1,4 2,4 3,4 4,4 … … … … … … … … … …

Рис. 11. Неограниченная шахматная доска

#include <iostream>

#include <cstdlib> //описание функции abs

int main(){

int x1, y1, x2, y2;

std::cin >> x1 >> y1 >> x2 >> y2;

int dx = abs(x1-x2), dy = abs(y1-y2);

bool tower = !dx || !dy ;

bool elephant = (dx == dy);

bool queen = tower || elephant;

bool king = (dx<=1 && dy<=1);

bool horse = (dx * dy == 2);

std::cout << tower + elephant + queen + king + horse;

}

В данном решении условие хода ладьи – совпадение координат по x или по y, в этих случаях величины dx и dy, определяемые как модуль разности соответствующих координат, обращаются в 0 или false. Достаточно очевидно определяются ходы всех фигур, кроме коня. Как известно, «конь ходит буквой Г». Это означает, что (dx==2 && dy==1) || (dx==1 && dy==2). В данном случае произведение dx и dy инвариант[11] равно 2.

Рассмотрим следующую задачу, которая также имеет отношение к шахматам.

Задача №22. Один в поле воин

Условие этой задачи очень простое: вам всего лишь надо определить, сколько клеток находится под боем шахматного коня, одиноко стоящего на шахматной доске размером N×N. На всякий случай напомним, что конь ходит буквой «Г» — на две клетки по горизонтали или вертикали в любом направлении, и потом на одну клетку в направлении, перпендикулярном первоначальному.

Входные данные

В первой строке записано натуральное число 4 ≤ N ≤ 25 – размер доски. Во второй строке координаты коня (маленькая латинская буква от 'a' до 'y' и число от 1 до 25) — стандартное шахматное обозначение клетки, на которой стоит конь. При этом буква обозначает вертикаль, а число — горизонталь.

Выходные данные

Выведите единственное число — количество клеток шахматной доски, находящихся под боем коня.

Пример

Ввод	Вывод
8 g6	6

Решение

Попробуем определить зависимость количества клеток, которые бьёт шахматный конь, от его координат. Для стандартной шахматной доски размером 8×8 это будет выглядеть так:

2 3 4 4 4 4 3 2 3 4 6 6 6 6 4 3 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 3 4 6 6 6 6 4 3 2 3 4 4 4 4 3 2

Несложно вывести зависимость для первой горизонтали:

dx = (1<x) + (2<x) + (x<n-1) + (x<n)

Аналогично для первой вертикали:

dy = (1<y)+(2<y)+(y<n-1)+(y<n)

Легко увидеть, число в координатах x,yопределяется как dx× dy / 2

#include <iostream>

int main() {

int n, y;

char c;

std::cin >> n >> c >> y;

int x = c - 'a' + 1;

int count = ((1<x) + (2<x) + (x<n-1) + (x<n))*

           ((1<y) + (2<y) + (y<n-1) + (y<n))/2;

std::cout << count;

}

При решении задачи использовалось арифметическое выражение

int x = c - 'a' + 1;

В данном случае от кода введенного символа отняли код латинской буквы ‘a’ и добавили 1. Так для символа ‘d’ эта величина x будет равна 4. Подробнее о символьном типе и действиях над ним будет рассказано далее в книге в соответствующей главе.

Задача №23. Зернышки

В банке находятся белые и черные зерна. Каждый раз из банки вынимают наугад два зернышка. Если они одинакового цвета, то их выбрасывают, а в банки кладут черное зерно (черных зерен достаточное количество). Если зерна разного цвета, то черное выбрасывают, а белое возвращают в банки. Эти действия повторяют, пока не останется одна зерно.

Напишите программу, которая по известному количеству черных и белых зерен определяет цвет последнего зернышка.

Входные данные. В единственной строке записаны два числа - количество белых и черных зерен.

Выходные данные. Единственная строка должна содержать цвет зерна, которое осталось: white - если зерно белое, black - если зерно черное.

Источник задачи: III этап Всеукраинской олимпиады по информатике 2011-2012 г.

Решение

Отметим, что при выборах черных (Ч) и белых (Б) зерен:

       Б + Б = Ч

       Ч + Ч = Ч

       Ч + Б = Б

При любом изменении количества белых зерен, их четность сохраняется. И это никак не зависит от числа черных зерен или порядка, в котором зерна выбираются. Т.о. если белых зерен было четное число, то их не останется, а последним зёрнышком останется чёрное. В другом случае, когда белых зёрен было нечетное число, последним оставшимся будет белое.

#include <iostream>

int main(){

int cntWhite, cntBlack;

std::cin >> cntWhite >> cntBlack;

std::cout << (cntWhite & 1 ? "white" : "black");

}

В условии cntWhite&1 выполняется побитовая операция И (конъюнкция). Она сработает следующим образом: допустим, cntWhite имеет значение 19, или в двоичной форме 10011

cntWhite	0	…	0	0	1	0	0	1	1
1	0	…	0	0	0	0	0	0	1
cntWhite&1	0	…	0	0	0	0	0	0	1

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

if (cntWhite % 2 == 1)…

или еще проще:

if (cntWhite % 2)…

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