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

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

Решение

Заметим, что число x нечетно только тогда, когда самый младший (то есть первый справа) бит в его двоичной записи равен 1. Докажем это. Вспомним знакомый со школьной статьи алгоритм перевода числа из двоичной системы в десятеричную. Он показан на следующей картинке:

Мы можем вынести два за скобку из всех слагаемых, кроме последнего, которое может принимать значение либо 1, либо 0. Таким образом, если оно равно нулю, то сумма будет иметь вид 2(…) = x, то есть будет делиться на два, а если оно будет равно единице, то сумма будет иметь вид 2(…)+1 = x, то есть не будет делиться на два. Это является критерием четности. Ч.т.д.

Итак, мы доказали факт того, что число нечетно, когда его младший бит равен 1, и четно, когда младший бит равен 0. Остался вопрос: как получить последний бит числа. Утверждение: последний бит числа x равен x&1, где & — побитовое И. Почему это так? И равно 1 только когда оба его аргумента равны 1. Число 1 в двоичной системе счисления имеет следующий вид: …000001 (в зависимости от того, скольки битными числами мы оперируем). А значит, при побитовом И единицы с числом х у результата все биты, кроме последнего, будут равны нулю, а последний бит будет равен 1, если в числе x он был равен 1 (1&1 = 1), и 0, если в числе x он был 0 (0&1 = 0).

Таким образом, значение выражения x&1 равно 1, если число x нечетное, и 0, если x четное.