Когда я занялся изучением Java, одной из первых задач, которую я пытался решить было определение четных/нечетных чисел. Я знал несколько способов как это сделать, но решил поискать «правильный» способ на просторах интернета. Информация по всем найденным ссылкам говорила мне об единственно правильном решении вида x % 2, с целью получения остатка от деления. Если в остатке 0 — число четное, если в остатке 1 — нечетное.
Со времен ZX Spectrum я помнил еще один способ и он связан с представлением числа в двоичной системе. Любое число в десятичной системе можно записать как сумму степеней двойки. Например, для одного байта, а это 8 бит, любое число в десятичной системе может быть представлено как сумма чисел 128+64+32+16+8+4+2+1.
Это просто последовательность степеней двойки. При переводе числа в двоичную систему, если нам нужно учитывать число, в двоичном представлении это будет единица, если не нужно, то это будет 0.
Например:
10 = 1010 (8+0+2+0)
13 = 1101 (8+4+0+1)
200 = 11001000 (128+64+0+0+8+0+0+0)
Сразу можно обратить внимание на то, что нечетное число может дать только нулевая степень двойки со значением 1, все остальные степени двойки будут четные по определению. Это автоматически означает, что с точки зрения двоичной системы счисления, если мы хотим проверить любое число на четность, нам не нужно проверять все число, какое бы большое оно не было. Нам нужно проверить только первый бит (самый правый). Если он 0, то число четное, так как все остальные биты дают четное число, и наоборот, если в самом правом бите единица, то число гарантировано нечетное, потому что все остальные биты дают только четное значение.
Чтобы проверить только правый бит в числе, можно использовать несколько способов. Один из них бинарный AND.
Со времен ZX Spectrum я помнил еще один способ и он связан с представлением числа в двоичной системе. Любое число в десятичной системе можно записать как сумму степеней двойки. Например, для одного байта, а это 8 бит, любое число в десятичной системе может быть представлено как сумма чисел 128+64+32+16+8+4+2+1.
Это просто последовательность степеней двойки. При переводе числа в двоичную систему, если нам нужно учитывать число, в двоичном представлении это будет единица, если не нужно, то это будет 0.
Например:
10 = 1010 (8+0+2+0)
13 = 1101 (8+4+0+1)
200 = 11001000 (128+64+0+0+8+0+0+0)
Сразу можно обратить внимание на то, что нечетное число может дать только нулевая степень двойки со значением 1, все остальные степени двойки будут четные по определению. Это автоматически означает, что с точки зрения двоичной системы счисления, если мы хотим проверить любое число на четность, нам не нужно проверять все число, какое бы большое оно не было. Нам нужно проверить только первый бит (самый правый). Если он 0, то число четное, так как все остальные биты дают четное число, и наоборот, если в самом правом бите единица, то число гарантировано нечетное, потому что все остальные биты дают только четное значение.
Чтобы проверить только правый бит в числе, можно использовать несколько способов. Один из них бинарный AND.