Проверка, содержит ли данная группа целых чисел значение 0

Question

Предположим, у меня есть несколько целых чисел (10 ~ 20), и мне нужно проверить, равно ли какое-либо из них 0. Какой самый эффективный способ сделать это? Я не хочу оценивать гигантский оператор if (a = 0 || b = 0 || c = 0 || ...). Я подумал об if (a b c ... = 0), но, если я правильно помню, умножение - не очень быстрый процесс. Есть ли еще какие-нибудь уловки, например побитовые операции, которые подойдут? Я стараюсь думать как можно ниже, чтобы сделать это супер эффективным.

Answer 1

Я почти уверен, что самый быстрый и ясный способ сделать это - использовать явный тест:

int has_zero = !a || !b || !c || !d || !e ...;

Поскольку || и && - это операторы замыкания в C, оценка прекращается, как только становится известен окончательный результат, поэтому, если (например) переменная b равна нулю, это удовлетворяет выражению как истинное и перестает оценивать остальные.

@ AbhayAravinda предположил, что !(a && b && c && d ...) может быть более эффективным, но я так не думаю; поскольку это не столько явное выполнение операции not, сколько низкоуровневый тест против нуля, это действительно простой тест для надежного выполнения практически любой архитектуры. Я быстро взглянул на оптимизированный ассемблер для обеих версий, и не было явного победителя по производительности, но я думаю, что первая версия более ясна.

Если каждый цикл имеет значение, проверьте обе версии на своей платформе, но в моей 64-битной системе Intel и g cc, и clang фактически генерируют одну и ту же сборку для обеих версий (с включенной оптимизацией).

Простой тестовый код:

int a, b, c, d, e, f;

int test_or()
{
    return !a || !b || !c || !d || !e || !f;
}

int test_and()
{
    return ! (a && b && c && d && e && f);
}


int main()
{
    return test_or() | test_and();
}

Скомпилируйте это с помощью gcc -S -O testfile.c и посмотрите на получившийся файл .s.

Answer 2

Проверяйте каждую по очереди. Используйте свойство короткого замыкания ||; поместите переменные в порядке убывания вероятности того, что каждая из них будет равна нулю:

if (!a/*most likely to be zero*/ || !b || ...){
    // one of them is zero
}

Answer 3

Вы можете посмотреть вывод ассемблера.

Команда !a || !b || !c || !d || !e || !f даст вам набор операторов cmp и je. По одной паре для каждой переменной. Из-за булевой оценки сокращения он может работать очень быстро. Или нет.

Возможно, лучшее и детерминированное c решение - это использование побитового оператора AND. Если один операнд равен 0, то результат будет 0. Таким образом, что-то вроде:

if (a & b & c & d & e & f & g & h & i & j & k)

приведет к одному mov, а затем and операторам для каждой переменной.

Итак , если переменная, равная 0, находится во второй половине оператора if, то побитовое И будет быстрее.

Answer 4

Большинство людей дают такой ответ:

!a || !b || ...

(где a - наиболее вероятное значение из нуля)

Идея состоит в том, что в случае, если a является ноль, то остальная часть последовательности не оценивается (из-за отсутствия необходимости), что является своего рода оптимизацией, выполняемой компилятором.

Это превращает вопрос в: выполняет ли ваш компилятор эту оптимизацию или нет (и в случае «возможно да», каковы параметры для обеспечения этого)?

Можете ли вы сказать нам, с каким компилятором (версией) вы работаете? Это может позволить нам проверить это.