Посчитать четные и нечетные цифры числа
Определить, сколько в числе четных цифр, а сколько нечетных. Число вводится с клавиатуры.
Решение задачи на языке программирования Python
Если число делится без остатка на 2, его последняя цифра четная. Увеличиваем на 1 счетчик четных цифр even . Иначе последняя цифра числа нечетная, увеличиваем счетчик нечетных цифр odd .
В Python операцию нахождения остатка от деления выполняет знак % .
Чтобы избавиться от младшего уже учтенного разряда, число следует разделить нацело на 10. Деление нацело обозначается двумя слэшами // .
a = int(input()) even = 0 odd = 0 while a > 0: if a % 2 == 0: even += 1 else: odd += 1 a = a // 10 print(f'Even: , odd: ')
65439 Even: 2, odd: 3
Кроме чисто математического подхода в Python можно решить задачу «через строку». Мы не будем переводить введенное строковое представление числа к целочисленному типу, вместо этого переберем символы строки в цикле for . Каждый символ преобразуем к числу и проверим на четность.
a = input() even = 0 odd = 0 for i in a: if int(i) % 2 == 0: even += 1 else: odd += 1 print("Even: %d, odd: %d" % (even, odd))
Поскольку количество четных (как и нечетных) цифр ограничено, в программу можно включить что-то типа «базы данных» и проверять каждый символ на вхождение в нее.
a = input() digits = "02468" even = 0 odd = 0 for i in a: if i in digits: even += 1 else: odd += 1 print("Even: %d, odd: %d" % (even, odd))
Обратим внимание, что оператор in языка Python в заголовке цикла for обозначает иное, чем в заголовке условного оператора. Логическое выражение i in digits возвращает истину если i входит в состав digits . В иных случаях — ложь.
X Скрыть Наверх
Решение задач на Python
Тестирование производительности кода в ОС Linux с примерами
Когда я занялся изучением 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.
AND
Бинарное И (AND) работает по следующему правилу. Если вы применяете к какому-либо числу, назовем его оригинальным, логическое AND с числом 0, то результат такой операции всегда 0. Таким образом можно обнулять ненужные вам биты. Если вы применяете к оригиналу 1, то вы получаете оригинал.
В двоичной системе это легко записать так:
0 AND 0 = 0 (обнуляем оригинал)
1 AND 0 = 0 (обнуляем оригинал)
0 AND 1 = 0 (не меняем оригинал)
1 AND 1 = 1 (не меняем оригинал)
Отсюда вытекают несколько простых правил.
Если мы к любому числу применим операцию AND всех единиц (все биты включены), то получим это же самое изначальное число.
Если мы к любому числу применим AND всех нолей (все биты выключены), то получим 0.
Если мы к байту 13 применим AND 0, то получим 0. В десятичном виде это выглядит как 13 AND 0 = 0
Если мы к байту 200 применим AND 0, то получим 0, или записывая кратко 200 AND 0 = 0
То же самое наоборот, применим к 13 все включенные биты, для байта это будет восемь единиц, и получим оригинал. В двоичной системе 00001101 AND 11111111 = 00001101 или в десятичной системе 13 AND 255 = 13
Для 200 будет соответственно 11001000 AND 11111111 = 11001000 или в десятичной системе 200 AND 255 = 200
Проверка бинарным способом
Для проверки числа на четность нам достаточно проверить только самый правый бит. Если он 0, то число четное, если 1, то не четное. Зная, что с помощью AND мы можем какие-то биты оставить оригинальными, а какие-то мы можем обнулить, мы можем просто обнулить все биты кроме самого правого. Например:
13 в двоичной системе это 1101. Применим к нему AND 0001 (обнуляем все биты, последний оставляем оригинальный). Меняем в числе 1101 все биты на 0 кроме последнего и получаем 0001. Мы получили только последний бит из нашего изначального числа. В десятичной системе это будет выглядеть как 13 AND 1 = 1.
То же самое с числом 200, в двоичном виде 11001000. Применим к нему AND 00000001, по той же схеме, обнуляем все биты, последний оставляем как есть, получаем 00000000, при этом левые 7 нулей мы обнулили командой AND, а последний 0 мы получили из оригинального числа. В десятичной системе это выглядит как 200 AND 1 = 0
Таким образом, применяя команду AND 1 к любому числу мы получаем, либо 0, либо 1. И если результат равен 0, то число четное. При 1 число нечетное.
В Java бинарное AND записывается как &. Соответственно, 200 & 1 = 0 (четное) и 13 & 1 = 1 (нечетное).
Отсюда вытекает, как минимум, два способа определения четных чисел.
X % 2 — через остаток от деления на два
X & 1 — через бинарное AND
Такие бинарные операции как OR, AND, XOR обрабатываются процессором за минимальное время. А вот операция деления это задача нетривиальная, и для того чтобы ее выполнить, процессору необходимо обработать множество инструкций, по сути выполнить целую программу. Однако, существуют операции бинарного сдвига влево и вправо, позволяющие, например, быстро делить число на 2. Вопрос в том, используют ли эту оптимизацию компиляторы и существует ли разница между этими двумя сравнениями, которые по факту делают то же самое.
Кодинг
Напишем программу, которая будет в цикле обрабатывать 9000000000 чисел по порядку, и определять их принадлежность к четному/нечетному через определение остатка от деления.
public class OddEvenViaMod < public static void main (String[] args) < long i=0; long odds=0; long evens=0; do < if ((i % 2) == 0) < evens++; >else < odds++; >i++; > while (i <9000000000L); System.out.println("Odd " + odds); System.out.println("Even " + evens); >> И напишем точно такую же, но поменяем буквально два символа, проверяя тоже самое через бинарное AND.
public class OddEvenViaAnd < public static void main (String[] args) < long i=0; long odds=0; long evens=0; do < if ((i & 1) == 0) < evens++; >else < odds++; >i++; > while (i<9000000000L); System.out.println("Odd " + odds); System.out.println("Even " + evens); Теперь нам нужно как-то сравнить эти две программы.
Ресурсы в Linux. CPU
На создание любой операционной системы потрачено гигантское количество часов, в частности на честное распределение ресурсов между программами. С одной стороны это хорошо, так как запуская две программы, вы можете быть уверены, что они будут работать параллельно, но с другой стороны, когда вам нужно проверить производительность программы, бывает крайне необходимо ограничить или хотя бы уменьшить внешнее влияние на программу со стороны других программ и операционной системы.
Первое, с чем предстоит разобраться — это процессор. ОС Linux для каждого процесса хранит побитовую маску, в которой указано, какие ядра могут использоваться приложением, а какие нет. Посмотреть и поменять эту маску можно командой taskset.
Например, посмотрим количество ядер у моего процессора:
[user@localhost]# grep -c processor /proc/cpuinfo 4 В моем компьютере установлен процессор с 4-мя ядрами. Это хорошо, потому что одно из них я собираюсь выделить под свои нужды.
Посмотрим, все ли из них используются на данный момент, командой top:
[user@localhost]# top Нажимаем «1», чтобы посмотреть информацию по каждому ядру отдельно:
top - 13:44:11 up 1 day, 23:26, 7 users, load average: 1.48, 2.21, 2.02 Tasks: 321 total, 1 running, 320 sleeping, 0 stopped, 0 zombie %Cpu0 : 7.7 us, 6.8 sy, 0.0 ni, 85.5 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st %Cpu1 : 9.2 us, 4.2 sy, 0.0 ni, 86.6 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st %Cpu2 : 7.6 us, 3.4 sy, 0.0 ni, 89.1 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st %Cpu3 : 8.4 us, 4.2 sy, 0.0 ni, 87.4 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st KiB Mem : 16210820 total, 296972 free, 10072092 used, 5841756 buff/cache KiB Swap: 16777212 total, 16777212 free, 0 used. 5480568 avail Mem . Тут мы видим, что все ядра используются примерно одинаково. (us и sy и id показатели примерно равны для каждого ядра).
Теперь попробуем посмотреть то же самое командой taskset.
[user@localhost]# taskset -p 1 pid 1's current affinity mask: f Битовая маска «F» в шестнадцатеричной системе означает 15 в десятеричной, или 1111 в двоичной (8+4+2+1). Все биты включены, а значит все ядра используются процессом с PID 1.
В ОС Linux, когда один процесс порождает другой системным вызовом clone, то битовая маска на момент клонирования копируется с родителя. Это означает, что если мы поменяем эту маску для нашего init процесса (в моем случае это systemd), то при запуске любого нового процесса через systemd этот новый процесс будет запущен уже с новой маской.
Поменять маску для процесса можно этой же командой, перечислив номера ядер CPU, которые мы хотим оставить используемыми для процесса. Допустим, мы хотим оставить нашему процессу ядра 0,2,3, а ядро 1 мы хотим отключить для нашего systemd процесса. Для этого нам надо выполнить команду:
[user@localhost]# taskset -pc 0,2,3 1 pid 1's current affinity list: 0-3 pid 1's new affinity list: 0,2,3 [user@localhost]# taskset -p 1 pid 1's current affinity mask: d Маска изменилась на «D» в шестнадцатеричной системе счисления, что равно 13 в десятеричной и равно 1101 в двоичной (8+4+0+1).
С этого момента любой процесс, который будет клонирован процессом systemd будет автоматически иметь маску 1101 использования CPU, а значит ядро с номером 1 использоваться не будет.
Запрещаем использование ядра всем процессам
Запрет основному процессу в Linux использования одного ядра отразится только на новых процессах, созданных этим процессом. Но у меня в системе уже не один процесс, а целое множество, такие как crond, sshd, bash и прочие. Если мне необходимо запретить всем процессам использования одного ядра, то я должен выполнить команду taskset для каждого запущенного процесса.
Для получения списка всех процессов воспользуемся API, которое нам дает ядро, а именно /proc файловая система.
Далее в цикле мы смотрим PID каждого запущенного процесса и меняем для него и всех тредов маску:
[user@localhost]# cd /proc; for i in `ls -d [0-9]*`; do taskset -a -pc 0,2,3 $i; done pid 1's current affinity list: 0,2,3 pid 1's new affinity list: 0,2,3 . Так как в ходе выполнения программы, какие-то процессы могли успеть породить другие процессы, то лучше эту команду запустить несколько раз.
Проверим результат нашей работы командой top:
[user@localhost]# top top - 14:20:46 up 2 days, 3 min, 7 users, load average: 0.19, 0.27, 0.57 Tasks: 324 total, 4 running, 320 sleeping, 0 stopped, 0 zombie %Cpu0 : 8.9 us, 7.7 sy, 0.0 ni, 83.4 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st %Cpu1 : 0.0 us, 0.0 sy, 0.0 ni,100.0 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st %Cpu2 : 9.5 us, 6.0 sy, 0.0 ni, 84.5 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st %Cpu3 : 8.4 us, 6.6 sy, 0.0 ni, 85.0 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st KiB Mem : 16210820 total, 285724 free, 10142548 used, 5782548 buff/cache KiB Swap: 16777212 total, 16777212 free, 0 used. 5399648 avail Mem Как видим картина немного поменялась, теперь для ядра 0,2,3 в среднем параметры us,sy,id у нас одинаковые, а для ядра 1 наше потребление ядра в userspace и sys равно 0, и ядро простаивает на все 100% (idle 100). Ядро 1 более не используется нашими приложениями и на очень небольшой процент используется на данный момент ядром.
Теперь задача тестирования производительности сводится к тому, чтобы запустить наш процесс на свободном ядре.
Память
Выделенная процессу физическая память может быть легко отнята у любого процесса. Этот механизм называется swap. Если ОС Linux имеет место для swap, она будет это делать в любом случае. Единственный способ запретить ОС отнимать память у нашего процесса, как и у любых других процессов, это полностью отключить раздел swap, что мы и сделаем:
[user@localhost]$ sudo swapoff -a [user@localhost]$ free -m total used free shared buff/cache available Mem: 15830 7294 1894 360 6641 7746 Swap: 0 0 0 Мы выделили 1 ядро процессора, которое не используется, и так же убрали у ядра Linux возможность делать swap памяти.
Диск
Для того чтобы снизить влияние диска на запуск нашего процесса, создадим диск в памяти и скопируем все необходимые файлы на этот диск.
Создаем директорию и монтируем файловую систему:
[user@localhost]$ sudo mkdir /mnt/ramdisk; [user@localhost]$ mount -t tmpfs -o size=512m tmpfs /mnt/ramdisk [user@localhost]$ chown user: /mnt/ramdisk Теперь надо разобраться с тем, что и как мы планируем запускать. Для того чтобы запустить нашу программу нам надо для начала откомпилировать наш код:
[user@localhost]$ javac OddEvenViaMod.java Затем надо запустить его:
[user@localhost]$ java OddEvenViaMod Но в нашем случае мы хотим запустить процесс на том ядре процессора, который не используется никаким другим процессом. Поэтому запускаем его через taskset:
[user@localhost]# taskset -c 1 time java OddEvenViaMod В наших тестах нам необходимо замерять время, поэтому наша строка запуска превращается в
taskset -c 1 time java OddEvenViaMod ОС Linux поддерживает несколько форматов запускаемых файлов, и самый распространённый из них ELF формат. Этот формат файла позволяет сказать ОС, чтобы она не запускала ваш файл, а запустила другой файл. На первый взгляд звучит не очень логично и понятно. Представим, что я запускаю игру Сапер, а запускается у меня игра Марио — это выглядит как вирус. Но в этом есть логика. Если моя программа требует какую-либо динамическую библиотеку, например libc, или же любую другую, это означает, что ОС должна сначала загрузить эту библиотеку в память, а уже после этого загрузить и запустить мою программу. И вроде бы логично такой функционал поместить в саму операционную систему, но операционная система работает в защищенной области памяти и должна содержать в себе настолько мало функционала, насколько это возможно и необходимо. Поэтому ELF формат предусматривает возможность сказать ОС, что мы хотим загрузить некую другую программу, а уже эта «другая» программа загрузит все необходимые библиотеки и нашу программу и запустит все это дело.
Итак, нам необходимо запустить 3 файла, это taskset, time, java.
Проверим первый из них:
[user@localhost]$ whereis taskset taskset: /usr/bin/taskset /usr/share/man/man1/taskset.1.gz Bash будет запускать файл /usr/bin/taskset, проверяем что внутри:
[user@localhost]$ file /usr/bin/taskset /usr/bin/taskset: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, BuildID[sha1]=7a2fd0779f64aa9047faa00f498042f0f0c5dc60, stripped Это ELF файл, о котором я писал выше. В ELF файле помимо самой программы присутствуют различные заголовки. Запуская этот файл ОС проверяет его заголовки, и если в файле существует заголовок «Requesting program interpreter», то ОС запустит файл именно из этого заголовка, а изначально запускаемый файл передаст в качестве аргумента.
Проверяем, существует ли в нашем ELF файле этот заголовок:
[user@localhost]$ readelf -a /usr/bin/taskset | grep -i interpreter [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2] Заголовок существует, а это значит, что запуская файл /usr/bin/taskset на самом деле мы запускаем /lib64/ld-linux-x86-64.so.2.
Проверим, что это за файл:
[user@localhost]$ ls -lah /lib64/ld-linux-x86-64.so.2 lrwxrwxrwx 1 root root 10 May 21 2019 /lib64/ld-linux-x86-64.so.2 -> ld-2.17.so Это сим линк на файл /lib64/ld-2.17.so. Проверяем его:
[user@localhost]$ file /lib64/ld-2.17.so /lib64/ld-2.17.so: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, BuildID[sha1]=a527fe72908703c5972ae384e78d1850d1881ee7, not stripped Как видим это другой ELF файл, который ОС будет запускать. Смотрим заголовки у него:
[user@localhost]$ readelf -a /lib64/ld-2.17.so | grep -i interpreter [user@localhost]$ Видим, что у этого ELF файла такого заголовка нет, значит ОС запустит этот файл и передаст управление ему. А уже этот файл откроет наш файл /usr/bin/taskset, прочитает оттуда информацию по всем необходимым библиотекам. Список необходимых библиотек так же находится в заголовках ELF файла. Мы можем посмотреть этот список командой ldd или readelf, что одно и то же:
[user@localhost]$ ldd /usr/bin/taskset linux-vdso.so.1 => (0x00007ffc4c1df000) libc.so.6 => /lib64/libc.so.6 (0x00007f4a24c4e000) /lib64/ld-linux-x86-64.so.2 (0x00007f4a2501b000) [user@localhost]$ readelf -a /usr/bin/taskset | grep NEEDED 0x0000000000000001 (NEEDED) Shared library: [libc.so.6] VDSO — это прилинкованный участок памяти не относящийся к библиотекам, потому отсутствует в ELF файле в качестве необходимой библиотеки.
Отсюда понятно, что программа /lib64/ld-2.17.so ответственна за запуск всех программ, которые ее требуют, а это все программы с динамически прилинкованными библиотеками.
Если мы запускаем /usr/bin/taskset — это абсолютно то же самое, что мы запустим /lib64/ld-2.17.so с агрументом /usr/bin/taskset.
Возвращаемся к проблеме влияния диска на наши тесты. Теперь мы знаем, что если хотим загружать нашу программу из памяти, то копировать нужно не один файл, а несколько:
[user@localhost]$ cp /lib64/libc-2.17.so /mnt/ramdisk/ [user@localhost]$ cp /lib64/ld-2.17.so /mnt/ramdisk/ [user@localhost]$ cp /usr/bin/taskset /mnt/ramdisk/ То же самое делаем для time, требования к библиотекам у которой точно такие же (ld и libc мы уже скопировали).
[user@localhost]$ cp /usr/bin/time /mnt/ramdisk/ Для java все немного сложнее, так как java требует много различных библиотек, которые можно долго копировать. Чтобы немного упростить себе жизнь, я скопирую всю директорию с моей java openjdk на диск в памяти и создам сим линк. Безусловно, обращения к диску в таком случае останутся, но их будет меньше.
[user@localhost]$ cp -R /usr/lib/jvm/java-1.8.0-openjdk-1.8.0.222.b10-0.el7_6.x86_64 /mnt/ramdisk/ Переименуем старую директорию, добавляя ей окончание .default
[user@localhost]$ sudo mv /usr/lib/jvm/java-1.8.0-openjdk-1.8.0.222.b10-0.el7_6.x86_64
И создадим симлинк:
[user@localhost]$ sudo ln -s /mnt/ramdisk/java-1.8.0-openjdk-1.8.0.222.b10-0.el7_6.x86_64 /usr/lib/jvm/ Как запустить бинарный файл мы уже знаем, через аргумент к файлу /lib64/ld-2.17.so, который запускается на самом деле. Но как заставить программу /lib64/ld-2.17.so загружать подгружаемые библиотеки из указанной нами директории? man ld нам в помощь, из которого мы узнаем, что если объявить переменную окружения LD_LIBRARY_PATH, то программа ld будет подгружать библиотеки из указанных нами директорий. Теперь у нас есть все данные чтобы подготовить строку запуска Java приложения.
Запускаем несколько раз подряд и проверяем:
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaMod Odd 4500000000 Even 4500000000 10.66user 0.01system 0:10.67elapsed 99%CPU (0avgtext+0avgdata 20344maxresident)k 0inputs+64outputs (0major+5229minor)pagefaults 0swaps [user@localhost ramdisk]$ [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaMod Odd 4500000000 Even 4500000000 10.65user 0.01system 0:10.67elapsed 99%CPU (0avgtext+0avgdata 20348maxresident)k 0inputs+64outputs (0major+5229minor)pagefaults 0swaps [user@localhost ramdisk]$ [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaMod Odd 4500000000 Even 4500000000 10.66user 0.01system 0:10.68elapsed 99%CPU (0avgtext+0avgdata 20348maxresident)k 0inputs+64outputs (0major+5229minor)pagefaults 0swaps [user@localhost ramdisk]$ [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaMod Odd 4500000000 Even 4500000000 10.65user 0.01system 0:10.67elapsed 99%CPU (0avgtext+0avgdata 20348maxresident)k 0inputs+96outputs (0major+5234minor)pagefaults 0swaps [user@localhost ramdisk]$ В ходе выполнения программы, мы можем запустить top и убедиться, что программа работает на нужном ядре CPU.
[user@localhost ramdisk]$ top . %Cpu0 : 19.7 us, 11.7 sy, 0.0 ni, 68.6 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st %Cpu1 :100.0 us, 0.0 sy, 0.0 ni, 0.0 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st %Cpu2 : 9.8 us, 9.1 sy, 0.0 ni, 81.1 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st %Cpu3 : 14.0 us, 9.0 sy, 0.0 ni, 77.1 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 s . Как видим результаты в большинстве случаев похожи. К сожалению, влияние ОС на ядро CPU полностью убрать мы не можем, поэтому результат все еще зависит от конкретных задач внутри ядра Linux на момент запуска. Поэтому лучше использовать медиану значений нескольких запусков.
В нашем случае мы видим, что программа на java обрабатывает 9000000000 с проверкой на четность через остаток от деления за 10.65 секунд на одном ядре CPU.
Проведем этот же тест с нашей второй программой, которая делает то же самое через бинарное AND.
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaAnd Odd 4500000000 Even 4500000000 4.02user 0.00system 0:04.03elapsed 99%CPU (0avgtext+0avgdata 20224maxresident)k 0inputs+64outputs (0major+5197minor)pagefaults 0swaps [user@localhost ramdisk]$ [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaAnd Odd 4500000000 Even 4500000000 4.01user 0.00system 0:04.03elapsed 99%CPU (0avgtext+0avgdata 20228maxresident)k 0inputs+64outputs (0major+5199minor)pagefaults 0swaps [user@localhost ramdisk]$ [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaAnd Odd 4500000000 Even 4500000000 4.01user 0.01system 0:04.03elapsed 99%CPU (0avgtext+0avgdata 20224maxresident)k 0inputs+64outputs (0major+5198minor)pagefaults 0swaps [user@localhost ramdisk]$ [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so java OddEvenViaAnd Odd 4500000000 Even 4500000000 4.02user 0.00system 0:04.03elapsed 99%CPU (0avgtext+0avgdata 20224maxresident)k 0inputs+64outputs (0major+5198minor)pagefaults 0swaps Теперь мы можем с уверенностью сказать, что сравнение на четность через бинарное AND занимает 4.02 секунды, а значит по сравнению с проверкой через остаток от деления, работает в 2.6 раза быстрее, как минимум на openjdk версии 1.8.0.
Oracle Java vs Openjdk
Я загрузил и распаковал java jdk с сайта oracle в директорию /mnt/ramdisk/jdk-13.0.2
[user@localhost ramdisk]$ /mnt/ramdisk/jdk-13.0.2/bin/javac OddEvenViaAnd.java [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/jdk-13.0.2/bin/java OddEvenViaAnd Odd 4500000000 Even 4500000000 10.39user 0.01system 0:10.41elapsed 99%CPU (0avgtext+0avgdata 24260maxresident)k 0inputs+64outputs (0major+6979minor)pagefaults 0swaps [user@localhost ramdisk]$ [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/jdk-13.0.2/bin/java OddEvenViaAnd Odd 4500000000 Even 4500000000 10.40user 0.01system 0:10.42elapsed 99%CPU (0avgtext+0avgdata 24268maxresident)k 0inputs+64outputs (0major+6985minor)pagefaults 0swaps Компилируем вторую программу:
[user@localhost ramdisk]$ /mnt/ramdisk/jdk-13.0.2/bin/javac OddEvenViaMod.java [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/jdk-13.0.2/bin/java OddEvenViaMod Odd 4500000000 Even 4500000000 10.39user 0.01system 0:10.40elapsed 99%CPU (0avgtext+0avgdata 24324maxresident)k 0inputs+96outputs (0major+7003minor)pagefaults 0swaps [user@localhost ramdisk]$ [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/jdk-13.0.2/bin/java OddEvenViaMod Odd 4500000000 Even 4500000000 10.40user 0.00system 0:10.41elapsed 99%CPU (0avgtext+0avgdata 24316maxresident)k 0inputs+64outputs (0major+6992minor)pagefaults 0swaps Время выполнения тех же исходников в jdk от oracle одинаковое для остатка от деления и бинарного AND, что выглядит нормальным, но это время одинаково плохое, которое было показано в openjdk на остатке от деления.
Python
Попробуем сравнить то же самое на языке Python. Сначала вариант с остатком от деления на 2:
odd=0 even=0 for i in xrange(100000000): if i % 2 == 0: even += 1 else: odd += 1 print "even", even print "odd", odd [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_mod.py even 50000000 odd 50000000 11.69user 0.00system 0:11.69elapsed 99%CPU (0avgtext+0avgdata 4584maxresident)k 0inputs+0outputs (0major+1220minor)pagefaults 0swaps [user@localhost ramdisk]$ [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_mod.py even 50000000 odd 50000000 11.67user 0.00system 0:11.67elapsed 99%CPU (0avgtext+0avgdata 4584maxresident)k 0inputs+0outputs (0major+1220minor)pagefaults 0swaps [user@localhost ramdisk]$ [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_mod.py even 50000000 odd 50000000 11.66user 0.00system 0:11.66elapsed 99%CPU (0avgtext+0avgdata 4584maxresident)k 0inputs+0outputs (0major+1220minor)pagefaults 0swaps Теперь тоже самое с бинарным AND:
odd=0 even=0 for i in xrange(100000000): if i & 1 == 0: even += 1 else: odd += 1 print "even", even print "odd", odd [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_and.py even 50000000 odd 50000000 10.41user 0.00system 0:10.41elapsed 99%CPU (0avgtext+0avgdata 4588maxresident)k 0inputs+0outputs (0major+1221minor)pagefaults 0swaps [user@localhost ramdisk]$ [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_and.py even 50000000 odd 50000000 10.43user 0.00system 0:10.43elapsed 99%CPU (0avgtext+0avgdata 4588maxresident)k 0inputs+0outputs (0major+1222minor)pagefaults 0swaps [user@localhost ramdisk]$ [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_and.py even 50000000 odd 50000000 10.43user 0.00system 0:10.43elapsed 99%CPU (0avgtext+0avgdata 4584maxresident)k 0inputs+0outputs (0major+1222minor)pagefaults 0swaps Результаты показывают, что AND быстрее.
На просторах интернета уже много раз писали, что глобальные переменные в Python работают медленней. Я решил сравнить время выполнения последней программы с AND и точно такой же, но обернутой в функцию:
def main(): odd=0 even=0 for i in xrange(100000000): if i & 1 == 0: even += 1 else: odd += 1 print "even", even print "odd", odd main() Запускаем в функции:
[user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_and_func.py even 50000000 odd 50000000 5.08user 0.00system 0:05.08elapsed 99%CPU (0avgtext+0avgdata 4592maxresident)k 0inputs+0outputs (0major+1222minor)pagefaults 0swaps [user@localhost ramdisk]$ [user@localhost ramdisk]$ export LD_LIBRARY_PATH=/mnt/ramdisk ; /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/taskset -c 1 /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/time /mnt/ramdisk/ld-2.17.so /mnt/ramdisk/python2.7 odd_and_func.py even 50000000 odd 50000000 5.08user 0.00system 0:05.09elapsed 99%CPU (0avgtext+0avgdata 4592maxresident)k 0inputs+0outputs (0major+1223minor)pagefaults 0swaps Как видим, одно и тоже сравнение на четность в Python через бинарное AND в функции обрабатывается 100000000 чисел на одном ядре CPU за ~ 5 секунд, такое же сравнение через AND без функции занимает ~ 10 секунд, и сравнение без функции через остаток от деления занимает ~ 11 секунд.
Почему Python программа в функции работает быстрее чем без нее, уже описывалось не раз и связанно с областью видимости переменных.
В Python есть возможность дизассемблировать программу на внутренние функции, которые Python использует при интерпретировании программы. Посмотрим какие функции использует Python для варианта с функцией odd_and_func.py:
[user@localhost ramdisk]# python Python 2.7.5 (default, Jun 20 2019, 20:27:34) [GCC 4.8.5 20150623 (Red Hat 4.8.5-36)] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> def main(): . odd=0 . even=0 . for i in xrange(100000000): . if i & 1 == 0: . even += 1 . else: . odd += 1 . print "even", even . print "odd", odd . >>> import dis >>> dis.dis(main) 2 0 LOAD_CONST 1 (0) 3 STORE_FAST 0 (odd) 3 6 LOAD_CONST 1 (0) 9 STORE_FAST 1 (even) 4 12 SETUP_LOOP 59 (to 74) 15 LOAD_GLOBAL 0 (xrange) 18 LOAD_CONST 2 (100000000) 21 CALL_FUNCTION 1 24 GET_ITER >> 25 FOR_ITER 45 (to 73) 28 STORE_FAST 2 (i) 5 31 LOAD_FAST 2 (i) 34 LOAD_CONST 3 (1) 37 BINARY_AND 38 LOAD_CONST 1 (0) 41 COMPARE_OP 2 (==) 44 POP_JUMP_IF_FALSE 60 6 47 LOAD_FAST 1 (even) 50 LOAD_CONST 3 (1) 53 INPLACE_ADD 54 STORE_FAST 1 (even) 57 JUMP_ABSOLUTE 25 8 >> 60 LOAD_FAST 0 (odd) 63 LOAD_CONST 3 (1) 66 INPLACE_ADD 67 STORE_FAST 0 (odd) 70 JUMP_ABSOLUTE 25 >> 73 POP_BLOCK 9 >> 74 LOAD_CONST 4 ('even') 77 PRINT_ITEM 78 LOAD_FAST 1 (even) 81 PRINT_ITEM 82 PRINT_NEWLINE 10 83 LOAD_CONST 5 ('odd') 86 PRINT_ITEM 87 LOAD_FAST 0 (odd) 90 PRINT_ITEM 91 PRINT_NEWLINE 92 LOAD_CONST 0 (None) 95 RETURN_VALUE И проверим то же самое без использования функции в нашем коде:
>>> f=open("odd_and.py","r") >>> l=f.read() >>> >>> l 'odd=0\neven=0\nfor i in xrange(100000000):\n\tif i & 1 == 0:\n\t\teven += 1\n\telse:\n\t\todd += 1\nprint "even", even\nprint "odd", odd\n' >>> k=compile(l,'l','exec') >>> k at 0x7f2bdf39ecb0, file "l", line 1> >>> dis.dis(k) 1 0 LOAD_CONST 0 (0) 3 STORE_NAME 0 (odd) 2 6 LOAD_CONST 0 (0) 9 STORE_NAME 1 (even) 3 12 SETUP_LOOP 59 (to 74) 15 LOAD_NAME 2 (xrange) 18 LOAD_CONST 1 (100000000) 21 CALL_FUNCTION 1 24 GET_ITER >> 25 FOR_ITER 45 (to 73) 28 STORE_NAME 3 (i) 4 31 LOAD_NAME 3 (i) 34 LOAD_CONST 2 (1) 37 BINARY_AND 38 LOAD_CONST 0 (0) 41 COMPARE_OP 2 (==) 44 POP_JUMP_IF_FALSE 60 5 47 LOAD_NAME 1 (even) 50 LOAD_CONST 2 (1) 53 INPLACE_ADD 54 STORE_NAME 1 (even) 57 JUMP_ABSOLUTE 25 7 >> 60 LOAD_NAME 0 (odd) 63 LOAD_CONST 2 (1) 66 INPLACE_ADD 67 STORE_NAME 0 (odd) 70 JUMP_ABSOLUTE 25 >> 73 POP_BLOCK 8 >> 74 LOAD_CONST 3 ('even') 77 PRINT_ITEM 78 LOAD_NAME 1 (even) 81 PRINT_ITEM 82 PRINT_NEWLINE 9 83 LOAD_CONST 4 ('odd') 86 PRINT_ITEM 87 LOAD_NAME 0 (odd) 90 PRINT_ITEM 91 PRINT_NEWLINE 92 LOAD_CONST 5 (None) 95 RETURN_VALUE Как видим, в варианте с объявленной функцией, Python использует внутренние функции с постфиксом FAST, например STORE_FAST, LOAD_FAST, а в варианте без объявления функции, Python использует внутренние функции STORE_NAME и LOAD_NAME.
Данная статья имеет мало практического смысла и нацелена скорее на понимание некоторых особенностей Linux, и компиляторов.
Программирование в Java 4
Как вы знаете программа выполняет все операции сверху-вниз
А что делать если программа должна в одном случае работать по одному, во втором по другому? Для решение этой проблемы изучим следующую тему.
Ветвления или Условные конструкции
Выражение if - (переводится как "если"), при помощи этого оператора мы можем выполнять блок кода, если условие верно.
if (Условие) < // Code >
Для работы с ветвлением нужно разобраться с еще одним типом данных и его операциями.
Логический Тип
boolean, он же логический тип
Данный тип работает только с двумя значениями - true (правда), false (ложь).
Пример:
Создадим переменную логического типа со значением true
boolean a = true;
Операции с логическим типом или Условные выражения
Все ниже перечисленные операции являются бинарными (работают только с двумя значениями) и всегда возвращают значения типа boolean, true - если условие верно, false - если не верно.
Сравнение на равенство, оператор "==".
- true - если значение ровны
- false - если значения разные
Обратите внимания, что "=" - это оператор присваивания значения, а "==" - это оператор равенства. Это одна из самых распространенных ошибок начинающих программистов. Пожалуйста не путайте их.
boolean a = 10 == 11;
Переменная а, будет ровна false.
Сравнение на неравенство, оператор "!=".
Полная противоположность оператора равенства.
- true - если значение разные
- false - если значения ровны
boolean a = 10 != 11;
Переменная а, будет ровна true.
Рассмотрим сразу несколько операторов, так как они очень похожи (к тому же их вы все знаете со школы)
Надеюсь, что вы и без меня понимаете как с ними работать.
Но все же вот пару примеров:
boolean a = 1 > 10; // false boolean b = 2 < 2; // false
А теперь не большой привет от математической логики. Не пугаемся, все нормально, ничего сложного.
Логическое И - "&&" - Конъюнкция
- Если два значения true - true
- В любой другом случае - false
boolean a = true && true; // true boolean b = false && true; // false
Логическое ИЛИ - "||" - Дизъюнкция
- Если любое из значений ровно true - true
- В любой другом случае - false
boolean a = true || true; // true boolean b = false || true; // true boolean c = false || false; // false
Логическое Исключающая ИЛИ (ЛИБО) - "^" - Строгая дизъюнкция
Честно говоря, этот оператор используется крайне редко (если конечно, речь идет не о криптографии), но все же стоит его знать.
- Если одно из значений будет true (но не одновременно) - false.
- в любом другом случае - false.
boolean a = true ^ false; // true boolean b = true ^ true; // false
Логическое НЕ - "!" - Инверсия
Данный оператор является унарным и работает только с одним значением
Операция инвертирует (устанавливает обратное) значение
- Если значения true - false
- Если false - true
boolean a = !false; // true boolean b = !true; // false
Приведу несколько примеров по теме:
boolean a = (10 + 2) < 6 || 2 == 2; // true boolean b = false ^ 2 < 1; // true boolean c = a & b; // true boolean d = 10 < 100 && -1 >2; // false boolean e = !((a && b) || c); // true
Теперь вернемся к ветвлению
Напомню синтаксис конструкции if:
if (Условие) < //code >
В условие принимается значение/выражение типа boolean, если значение ровно true - блок кода внутри фигурных скобок выполнится, в другом случае - будет игнорироваться.
Пример:
Проверяем число на четность
Scanner in = new Scanner(System.in); System.out.println("Введите число, для проверки на четность"); int input = in.nextInt(); if (input % 2 == 0) < System.out.println("Число четное"); >if (!(input % 2 == 0))
- Для начала мы подключаем сканер.
- Выводим сообщение, где просим ввести число.
- Читаем вводное значение и записываем в переменную input.
- Условие: если вводное значение делим по модулю на 2 и получаем 0, выводим сообщение, что число четное. (иными словами если число делится на 2 без остатка)
- Условие: такое же условие только в начале стоит оператор НЕ (!), то есть если условие не верное выводим сообщение, что число не четное.
Конструкция else (иначе)
Используется вместе с конструкцией if позволяет выполнить блок кода, если условие if - false.
if (Условие) < // Выполняемый код, если условие верное >else < // Выполняемый код, если условие не верное >
В качестве примера можно переписать прошлый пример с использованием else (как и нужно было писать эту программу):
Scanner in = new Scanner(System.in); System.out.println("Введите число, для проверки на четность"); int input = in.nextInt(); if (input % 2 == 0) < System.out.println("Число четное"); >else
А как бы вы решили такую задачу:
Вводится число, если оно четное выводим 1, если нет, выводим 2, если число четное и больше 3-х выводим 3.
Предполагаю, что некоторые будут пытаться написать примерно так:
Scanner in = new Scanner(System.in); System.out.println("Введите число, для проверки на четность"); int input = in.nextInt(); if (input % 2 == 0) < System.out.println("1"); >else < System.out.println("2"); >if (input % 2 == 0 && input > 10)
Давайте разберем, что здесь не так
если мы вводим нечетное число - все хорошо, выведется 2
и если введем четное число, но меньше 10 - выведется 1,
а вот если вводим четное число больше 10 - выведется и 1, и 3
Почему так происходит? Ответ прост, потому что так написана программа. Например если вводится число 12 подойдет к первому условию и к третьему.
На самом деле логика должна быть примерно такая:
Проверяем число на четность
Если четное, то
проверяем больше ли оно 10-ти
Если больше - выводим 3
Если нет - выводим 1
Если не четное, то выводим 2
А вот и сам код программы:
Scanner in = new Scanner(System.in); System.out.println("Введите число, для проверки на четность"); int input = in.nextInt(); if (input % 2 == 0) < if (input % 2 == 0 && input >10) < System.out.println("3"); >System.out.println("1"); > else
Конструкция else if
Предположим, что у вас в программе есть момент, когда идет множество ветвлений и вам приходится писать несколько условий подряд.
К примеру, обработчик какой-то команды (как в командной строке), пользователь вводит команду и программа как-то реагирует на это.
Для этого отлично подходит конструкция else if.
if (Условие 1) < // Code 1. >else if (Условие 2) < // Code 2. >else if (Условие 3) < // Code 3. >else < // Code 4. >
Как это будет работать:
- Если 1 условие верное - выполняется code 1
- Если 1 условие не верное, следует условие 2, если оно верное - выполняется code 2
- Если условие 2 не верное, следует условие 3, если оно верное - выполняется code 3
- Если условие 3 не верное -выполняется code 4
Разберем на примере программы, которая будет выводит расписание занятий для конкретной группы.
Идея такая: У нас есть факультет "Программирования", на ней учится 3 группы (для простоты с номерами 1, 2, 3) . Программа будет спрашивать группу, в ответ выдавать - расписание занятий на завтра.
Для начала давайте спросим у пользователя, для какой группы расписание ему нужно.
System.out.println("Введите номер группы");
Затем нужно считать данные, которые ввел пользователь.
Scanner in = new Scanner(System.in); int groupNumber = in.nextInt();
Далее нам нужно судя из ответа, вывести нужно расписание. Тут мы и будем использовать конструкцию else if.
if (groupNumber == 1) < System.out.println("Расписание для первой группы"); >else if (groupNumber == 2) < System.out.println("Расписание для второй группы"); >else if (groupNumber == 3) < System.out.println("Расписание для третей группы"); >else
Здесь вы можете посмотреть полный код программы
Конструкция Switch
В некоторых случаях из-за конструкции else if код может стать слишком громоздким и излишним, конструкция switch помогает решить эту проблему.
Работа switch аналогична.
switch (Принимаемое значение) < case 1: // Code 1.. break; case 2: // Code 2.. break; case 3: // Code 3.. break; default: // Code 4.. >
Здесь дела обстоят также как и в примере выше (про if else), но немного меняется принцип.
В "принимаемые значение" можно вставить переменную/значение, далее идут несколько case'ов, "принимаемое значение" сравнивается со всеми значениями написанные после оператора case, если они ровны - выполняется код после ":" до оператора break, если не один не подошел - выполняется код после оператора default (оператор default может отсутствовать).
В качестве примера предлагаю переписать пример выше (с использованием else if).
// ПОправить скин (забыл sout)
Напишите программу, проверяющую число на четность, используя только битовые операции
В этой задаче вам необходимо реализовать функцию, которая бы проверяла число на четность, используя только битовые операции 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 четное.