Вы бы использовали num% 2 или num & 1, чтобы проверить, является ли число четным? - PullRequest
18 голосов
/ 23 декабря 2009

Ну, есть по крайней мере два низкоуровневых способа определить, является ли данное число четным или нет:

 1. if (num%2 == 0) { /* even */ } 
 2. if ((num&1) == 0) { /* even */ }

Я считаю, что второй вариант гораздо более элегантный и содержательный, и я обычно использую его. Но это не только вопрос вкуса; Фактическая производительность может варьироваться: обычно побитовые операции (такие как логические и здесь) гораздо более эффективны, чем операции с модами (или div). Конечно, вы можете утверждать, что некоторые компиляторы смогут оптимизировать его в любом случае, и я согласен ... но некоторые не будут.

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

Что ты думаешь?

Указанные два фрагмента верны, только если num является либо беззнаковым целым числом, либо отрицательным числом с представлением дополнения до двух. - Как справедливо говорится в некоторых комментариях.

Ответы [ 12 ]

74 голосов
/ 23 декабря 2009

Сначала я пишу код для читабельности, поэтому мой выбор здесь num % 2 == 0. Это гораздо яснее, чем num & 1 == 0. Я позволю компилятору беспокоиться об оптимизации для меня и настрою только, если профилирование покажет, что это узкое место. Все остальное преждевременно.

Я считаю второй вариант гораздо более элегантным и значимым

Я категорически не согласен с этим. Число даже потому, что его конгруэнтность по модулю два равна нулю, а не потому, что его двоичное представление заканчивается определенным битом. Двоичные представления - это деталь реализации. Опираясь на детали реализации, как правило, запах кода. Как уже отмечали другие, тестирование LSB дает сбой на машинах, которые используют свои дополняющие представления.

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

Я не согласен. Мы все должны писать код, чтобы прояснить наши намерения. Если мы проверяем на равномерность, код должен выразить это (и комментарий должен быть ненужным). Опять же, проверка соответствия по модулю два более четко выражает намерение кода, чем проверка LSB.

И, что более важно, детали должны быть скрыты методом isEven. Таким образом, мы должны видеть if(isEven(someNumber)) { // details } и видеть num % 2 == 0 только один раз в определении isEven.

22 голосов
/ 23 декабря 2009

Если вы собираетесь сказать, что некоторые компиляторы не будут оптимизировать %2, то вы также должны заметить, что некоторые компиляторы используют представление дополнения единиц для целых чисел со знаком. В этом представлении &1 дает неправильный ответ для отрицательных чисел.

Итак, что вы хотите - код, который работает медленно на «некоторых компиляторах», или код, который ошибочен на «некоторых компиляторах»? Не обязательно одинаковые компиляторы в каждом случае, но оба вида встречаются крайне редко.

Конечно, если num имеет тип без знака или один из целочисленных типов C99 с фиксированной шириной (int8_t и т. Д., Которые должны быть дополнением до 2), то это не проблема. В этом случае я считаю %2 более элегантным и осмысленным, а &1 - хаком, который иногда может понадобиться для производительности. Я думаю, например, что CPython не выполняет эту оптимизацию, и то же самое будет справедливо для полностью интерпретируемых языков (хотя тогда накладные расходы на синтаксический анализ, вероятно, уменьшат разницу между двумя машинными инструкциями). Я был бы немного удивлен, столкнувшись с компилятором C или C ++, который не делал этого там, где это было возможно, потому что это не представляет сложности с точки зрения выдачи инструкций, если не раньше.

В целом, я бы сказал, что в C ++ вы полностью зависите от способности компилятора оптимизировать. Стандартные контейнеры и алгоритмы имеют n уровней косвенности, большинство из которых исчезает, когда компилятор заканчивает вставку и оптимизацию. Приличный компилятор C ++ может обрабатывать арифметику с постоянными значениями до завтрака, а приличный компилятор C ++ будет генерировать мусорный код независимо от того, что вы делаете.

12 голосов
/ 23 декабря 2009

Я определяю и использую функцию «IsEven», поэтому мне не нужно об этом думать, затем я выбрал один или другой метод и забыл, как проверить, является ли что-то четным.

Только придирка / предостережение: я бы просто сказал, что с побитовой операцией вы предполагаете что-то о представлении чисел в двоичном формате, а по модулю - нет. Вы интерпретируете число как десятичное значение. Это в значительной степени гарантировано для работы с целыми числами. Однако учтите, что модуль будет работать для двойного числа, а побитовая операция - нет.

10 голосов
/ 23 декабря 2009

Ваш вывод о производительности основан на популярной ложной предпосылке.

По какой-то причине вы настаиваете на переводе языковых операций в их «очевидные» машинные аналоги и делаете выводы о производительности на основе этого перевода. В этом конкретном случае вы пришли к выводу, что побитовая и & операция языка C ++ должна быть реализована побитовой и машинной операцией, в то время как операция по модулю % должна как-то включать машинное деление, которое предположительно медленнее. Такой подход имеет очень ограниченное применение, если таковой имеется.

Во-первых, я не могу представить реальный компилятор C ++, который интерпретировал бы языковые операции таким «буквальным» способом, то есть отображая их в «эквивалентные» машинные операции. В основном потому, что чаще, чем вы думаете, эквивалентные машинные операции просто не существуют.

Когда речь идет о таких базовых операциях с непосредственной константой в качестве операнда, любой уважающий себя компилятор всегда сразу «поймет», что и num & 1, и num % 2 для целого num делают абсолютно одно и то же, что заставит компилятор генерировать абсолютно одинаковый код для обоих выражений. Нет необходимости добавлять, что производительность будет точно такой же.

Кстати, это не называется «оптимизация». Оптимизация, по определению, это когда компилятор решает отклониться от стандартного поведения абстрактной машины C ++, чтобы сгенерировать более эффективный код (сохраняя наблюдаемое поведение программы). В этом случае нет отклонений, что означает отсутствие оптимизации.

Более того, вполне возможно, что на данной машине наиболее оптимальным способом реализации обоих является ни побитовое, ни деление, а некоторые другие специальные машинно-ориентированные инструкции. Кроме того, вполне возможно, что в какой-либо инструкции вообще не будет необходимости, поскольку четность / нечетность определенного значения может быть предоставлена ​​«бесплатно» с помощью флагов состояния процессора или чего-то подобного что.

Другими словами, аргумент эффективности недействителен.

Во-вторых, чтобы вернуться к исходному вопросу, более предпочтительным способом определения четности / нечетности значения, безусловно, является подход num % 2, поскольку он реализует необходимую проверку буквально («по определению») и четко выражает тот факт, что проверка является чисто математической. То есть ясно, что мы заботимся о свойстве числа , а не о свойстве представления (как в случае варианта num & 1).

Вариант num & 1 должен быть зарезервирован для ситуаций, когда вы хотите получить доступ к битам представления значения числа. Использование этого кода для проверки четности / нечетности является крайне сомнительной практикой.

9 голосов
/ 23 декабря 2009

Неоднократно упоминалось, что любой современный компилятор создает одну и ту же сборку для обеих опций. Это напомнило мне о демонстрационной странице LLVM , которую я видел где-то на днях, так что я решил попробовать. Я знаю, что это не более чем анекдотичный, но он подтверждает то, что мы ожидали: x%2 и x&1 реализованы одинаково.

Я также попытался скомпилировать их с помощью gcc-4.2.1 (gcc -S foo.c), и результирующая сборка идентична (и вставлена ​​внизу этого ответа).

Запрограммируйте первое:

int main(int argc, char **argv) {
  return (argc%2==0) ? 0 : 1;
}

Результат:

; ModuleID = '/tmp/webcompile/_27244_0.bc'
target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"
target triple = "i386-pc-linux-gnu"

define i32 @main(i32 %argc, i8** nocapture %argv) nounwind readnone {
entry:
    %0 = and i32 %argc, 1       ; <i32> [#uses=1]
    ret i32 %0
}

Запрограммируйте второе:

int main(int argc, char **argv) {
  return ((argc&1)==0) ? 0 : 1;
}

Результат:

; ModuleID = '/tmp/webcompile/_27375_0.bc'
target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"
target triple = "i386-pc-linux-gnu"

define i32 @main(i32 %argc, i8** nocapture %argv) nounwind readnone {
entry:
    %0 = and i32 %argc, 1       ; <i32> [#uses=1]
    ret i32 %0
}

Выход GCC:

.text
.globl _main
_main:
LFB2:
  pushq %rbp
LCFI0:
  movq  %rsp, %rbp
LCFI1:
  movl  %edi, -4(%rbp)
  movq  %rsi, -16(%rbp)
  movl  -4(%rbp), %eax
  andl  $1, %eax
  testl %eax, %eax
  setne %al
  movzbl  %al, %eax
  leave
  ret
LFE2:
  .section __TEXT,__eh_frame,coalesced,no_toc+strip_static_syms+live_support
EH_frame1:
  .set L$set$0,LECIE1-LSCIE1
  .long L$set$0
LSCIE1:
  .long 0x0
  .byte 0x1
  .ascii "zR\0"
  .byte 0x1
  .byte 0x78
  .byte 0x10
  .byte 0x1
  .byte 0x10
  .byte 0xc
  .byte 0x7
  .byte 0x8
  .byte 0x90
  .byte 0x1
  .align 3
LECIE1:
.globl _main.eh
_main.eh:
LSFDE1:
  .set L$set$1,LEFDE1-LASFDE1
  .long L$set$1
ASFDE1:
  .long LASFDE1-EH_frame1
  .quad LFB2-.
  .set L$set$2,LFE2-LFB2
  .quad L$set$2
  .byte 0x0
  .byte 0x4
  .set L$set$3,LCFI0-LFB2
  .long L$set$3
  .byte 0xe
  .byte 0x10
  .byte 0x86
  .byte 0x2
  .byte 0x4
  .set L$set$4,LCFI1-LCFI0
  .long L$set$4
  .byte 0xd
  .byte 0x6
  .align 3
LEFDE1:
  .subsections_via_symbols
6 голосов
/ 23 декабря 2009

Все зависит от контекста. Я на самом деле предпочитаю подход & 1, если это системный контекст низкого уровня. Во многих из этих типов контекстов "даже" в основном означает, что для меня младший бит равен нулю, а не делится на два.

ОДНАКО: у вашего лайнера есть ошибка.

Вы должны идти

if( (x&1) == 0 )

не

if( x&1 == 0 )

Последнее ANDs x с 1 == 0, то есть это ANDs x с 0, что приводит к 0, что, конечно, всегда оценивается как ложное.

Так что, если вы сделали это именно так, как вы предлагаете, все числа будут нечетными!

4 голосов
/ 23 декабря 2009

Любой современный компилятор оптимизирует работу по модулю, поэтому скорость не имеет значения.

Я бы сказал, что использование модуля по модулю облегчит понимание, но создание функции is_even, использующей метод x & 1, даст вам лучшее из обоих миров.

3 голосов
/ 23 декабря 2009

Они оба довольно интуитивно понятны.

Я бы дал небольшое преимущество num % 2 == 0, но у меня действительно нет предпочтений. Конечно, что касается производительности, то, вероятно, это микрооптимизация, поэтому я бы не беспокоился об этом.

1 голос
/ 10 августа 2014

Я потратил лет , настаивая на том, что любой разумный компилятор, достойный места на диске, оптимизирует num % 2 == 0 до num & 1 == 0. Затем, проанализировав разборку по другой причине, у меня была возможность проверить мои предположения.

Оказывается, я был не прав. Microsoft Visual Studio , вплоть до версии 2013, генерирует следующий объектный код для num % 2 == 0:

    and ecx, -2147483647        ; the parameter was passed in ECX
    jns SHORT $IsEven
    dec ecx
    or  ecx, -2
    inc ecx
$IsEven:
    neg ecx
    sbb ecx, ecx
    lea eax, DWORD PTR [ecx+1]

Да, действительно. Это в режиме Release со всеми включенными оптимизациями. Вы получаете практически эквивалентные результаты, будь то сборка для x86 или x64. Вы, вероятно, не поверите мне; Я сам едва поверил в это.

Он делает то, что вы ожидаете от num & 1 == 0:

not  eax                        ; the parameter was passed in EAX
and  eax, 1

Для сравнения GCC (начиная с версии 4.4) и Clang (начиная с версии 3.2) делают то, что можно было ожидать, генерируя идентичный объект код для обоих вариантов. Однако, согласно интерактивному компилятору Мэтта Годболта , ICC 13.0.1 также не поддается моим ожиданиям.

Конечно, эти компиляторы не неправильны . Это не ошибка. Есть много технических причин (как было указано в других ответах), почему эти два фрагмента кода не идентичны. И, безусловно, здесь следует привести аргумент «преждевременная оптимизация - зло». Конечно, есть причина, по которой мне потребовались годы, чтобы заметить это, и даже тогда я случайно наткнулся на нее.

Но, , как сказал Дуг Т. , вероятно, лучше определить где-нибудь в вашей библиотеке функцию IsEven, которая исправит все эти маленькие детали, чтобы вам никогда не приходилось думать о них снова. - и держать ваш код читабельным. Если вы регулярно ориентируетесь на MSVC, возможно, вы определите эту функцию так, как я это сделал:

bool IsEven(int value)
{
    const bool result = (num & 1) == 0;
    assert(result == ((num % 2) == 0));
    return result;   
}
0 голосов
/ 23 декабря 2009

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

Кроме того, если только этот код не запускается в системе, которая действительно ограничена в ресурсах (я думаю, микроконтроллер), не пытайтесь оптимизировать под оптимизатор компилятора.

...