Преобразует ли большинство компиляторов % 2 в сравнение битов? Это действительно быстрее?


В программировании часто требуется проверить, является ли число нечетным или четным. Для этого мы обычно используем:

n % 2 == 0

Однако, насколько я понимаю, оператор '%' фактически выполняет деление и возвращает его остаток; поэтому для случая выше, было бы быстрее просто проверить последний бит вместо этого. Скажем n = 5;

5 = 00000101

Чтобы проверить, является ли число нечетным или четным, нам просто нужно проверить последний бит. Если это 1, то число нечетное; в противном случае оно четное. В программирование, оно было бы выражено следующим образом:

n & 1 == 0

В моем понимании это было бы быстрее, чем % 2, поскольку никакого разделения не выполняется. Требуется простое сравнение битов.

Тогда у меня есть 2 вопроса:

1) Действительно ли второй путь быстрее первого (во всех случаях)? 2) Если ответ на 1-да, то достаточно ли умны компиляторы (на всех языках), чтобы преобразовать % 2 в простое сравнение битов? Или мы должны явно использовать второй способ, если мы хотим лучшего представление?
2   8   2015-08-17 00:05:53

2 ответа:

Да, битовый тестнамного быстрее, чем целочисленное деление, примерно в 10-20 раз или даже в 100 раз для 128bit / 64bit = 64bit idiv на Intel . Исп.. поскольку x86, по крайней мере, имеет инструкцию test, которая устанавливает флаги условий на основе результата побитового и, поэтому вам не нужно делить и затем сравнивать; побитовое AND это сравнение.

Я решил на самом деле проверить выходные данные компилятора на Godbolt , и получил сюрприз:

Оказывается, что использование n % 2 в качестве знакового целого значения (например, return n % 2 из функции, возвращающей signed int) вместо того, чтобы просто проверить его на ненулевое (if (n % 2)), иногда приводит к более медленному коду, чем return n & 1. Это происходит потому, что (-1 % 2) == -1, в то время как (-1 & 1) == 1, поэтому компилятор не может использовать побитовое и. Компиляторы по-прежнему избегают целочисленного деления и используют вместо него некоторые хитроумные последовательности shift / and / add / sub, потому что это все равно дешевле, чем целочисленное деление. (gcc и clang используют разные последовательности.)

Поэтому, если вы хотите вернуть значение истинности, основанное на n % 2, Лучше всего сделать это с типом без знака. Это позволяет компилятору всегда оптимизировать его до одной и инструкции. (На godbolt вы можете переключиться на другие архитектуры, такие как ARM и PowerPC, и увидеть, что unsigned even (%) функция и функция int even_bit (побитовая &) имеют один и тот же код asm.)

Использование bool (которое должно быть 0 или 1, а не просто любое ненулевое значение) - это еще один вариант, но компилятор придется проделать дополнительную работу, чтобы вернуть (bool) (n % 4) (или любой другой тест, кроме n%2). Побитовая-и версия этого будет 0, 1, 2 или 3, поэтому компилятор должен превратить любое ненулевое значение в 1. (x86 имеет эффективную инструкцию setcc, которая устанавливает регистр в 0 или 1, в зависимости от флагов, поэтому это все еще только 2 инструкции вместо 1. clang/gcc использует это, см. aligned4_bool в выходных данных godbolt asm.)

С любым уровнем оптимизации выше, чем -O0, gcc и clang оптимизируют if (n%2) до того, что мы ожидать. Другой большой сюрприз заключается в том, что icc 13не . я не понимаю WTF icc думает, что это происходит со всеми этими ветвями.

Скорость эквивалентна.

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

Используйте то, что вам кажется наиболее читаемым.