Найти максимум три числа в C без использования условного оператора и тройного оператора

Ответ 1

Использование короткого замыкания в булевых выражениях:

int max(int a, int b, int c)
{
     int m = a;
     (m < b) && (m = b); //these are not conditional statements.
     (m < c) && (m = c); //these are just boolean expressions.
     return m;
}

Объяснение:

В логической операции AND, такой как x && y, y оценивается тогда и только тогда, когда x истинно. Если x является ложным, то y не оценивается, потому что все выражение будет ложным, которое можно вывести, даже не оценивая y. Это называется короткозамкнутым, когда значение логического выражения можно вывести без оценки всех операндов в нем.

Примените этот принцип к вышеуказанному коду. Первоначально m a. Теперь, если (m < b) истинно, то это означает, что b больше, чем m (на самом деле это a), поэтому второе подвыражение (m = b) оценивается и m устанавливается на b. Если, однако, (m < b) является ложным, то второе подвыражение не будет оцениваться, а m останется a (что больше, чем b). Аналогичным образом оценивается второе выражение (на следующей строке).

Короче говоря, вы можете прочитать выражение (m < x) && (m = x) следующим образом: установите m в x тогда и только тогда, когда m меньше x, т.е. (m < x) равно правда. Надеюсь, это поможет вам понять код.

Тестовый код:

int main() {
        printf("%d\n", max(1,2,3));
        printf("%d\n", max(2,3,1));
        printf("%d\n", max(3,1,2));
        return 0;
}

Вывод:

3
3
3

Онлайн-демонстрация: http://www.ideone.com/8045P

Обратите внимание, что реализация max дает предупреждения, поскольку оцениваемые выражения не используются:

prog.c: 6: предупреждение: вычисленное значение не используется
prog.c: 7: предупреждение: вычисленное значение не используется

Чтобы избежать этих (безобидных) предупреждений, вы можете реализовать max как:

int max(int a, int b, int c)
{
     int m = a;
     (void)((m < b) && (m = b)); //these are not conditional statements.
     (void)((m < c) && (m = c)); //these are just boolean expressions.
     return m;
}

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

• http://www.ideone.com/PZ1sP

Ответ 2

Предполагая, что вы имеете дело с целыми числами, как насчет:

#define max(x,y) (x ^ ((x ^ y) & -(x < y)))
int max3(int x, int y, int z) {
    return max(max(x,y),z);
}

Ответ 3

Просто добавьте еще одну альтернативу, чтобы избежать условного выполнения (это не тот, который я бы использовал, но, казалось, отсутствовал из набора решений):

int max( int a, int b, int c ) {
   int l1[] = { a, b };
   int l2[] = { l1[ a<b ], c };
   return l2[ l2[0] < c ];
}

Этот подход использует (как и большинство других) тот факт, что результат булевого выражения при преобразовании в int дает либо 0, либо 1. Упрощенная версия для двух значений будет:

int max( int a, int b ) {
   int lookup[] { a, b };
   return lookup[ a < b ];
}

Если выражение a<b верно, вернем b, тщательно сохраненный в первом индексе массива поиска. Если выражение дает false, мы возвращаем a, который хранится как элемент 0 массива lookup. Используя это как строительный блок, вы можете сказать:

int max( int a, int b, int c ) {
   int lookup[ max(a,b), c ];
   return lookup[ max(a,b) < c ];
}

Который может быть тривиально преобразован в код выше, избегая второго вызова внутреннего max, используя результат, уже сохраненный в lookup[0], и вставляя исходный вызов max(int,int).

(Эта часть - просто еще одно доказательство, которое вы должны измерить, прежде чем перейти к выводам, см. редактирование в конце)

Что касается того, что я бы на самом деле использовал... ну, возможно, тот, что @Foo Baa здесь изменен, чтобы использовать встроенную функцию, а не макрос. Следующий вариант будет либо здесь, либо с помощью @MSN здесь.

Общий знаменатель этих трех решений, не присутствующих в принятом ответе, состоит в том, что они не только избегают синтаксической конструкции if, либо тройного оператора ?:, но что они вообще избегают ветвления и могут иметь влияние на производительность. Прогнозирующий ветвь в CPU не может отсутствовать, когда нет ветвей.

При рассмотрении производительности сначала измерьте, а затем подумайте

Я фактически реализовал несколько различных вариантов для 2-way max и проанализировал сгенерированный код компилятором. Следующие три решения генерируют один и тот же код сборки:

int max( int a, int b ) { if ( a < b ) return b; else return a; }
int max( int a, int b ) { return (a < b? b : a ); }
int max( int a, int b ) {
   (void)((a < b) && (a = b));
   return a;
}

Это не удивительно, так как все три представляют собой ту же самую операцию. Интересный бит информации состоит в том, что сгенерированный код не содержит никакой ветки. Реализация проста с инструкцией cmovge (тест, выполненный с помощью g++ на платформе Intel x64):

movl    %edi, %eax       # move a into the return value
cmpl    %edi, %esi       # compare a and b
cmovge  %esi, %eax       # if (b>a), move b into the return value
ret

Фокус в условной инструкции перемещения, что позволяет избежать любой потенциальной ветки.

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

Ответ 4

ОБНОВЛЕНИЕ: Глядя на это через 4 года, я вижу, что это плохо, если два или более значений оказываются равными. Замена > на >= изменяет поведение, но не устраняет проблему. Он все еще может быть спасен, поэтому я еще не удалю его, но не использую его в производственном коде.

Хорошо, здесь моя:

int max3(int a, int b, int c)
{
    return a * (a > b & a > c) +
           b * (b > a & b > c) +
           c * (c > a & c > b);
}

Обратите внимание, что использование &, а не && исключает любой условный код; он полагается на то, что > всегда дает 0 или 1. (Код, сгенерированный для a > b, может включать условные переходы, но они не видны с C.)

Ответ 5

int fast_int_max(int a, int b)
{
    int select= -(a < b);
    unsigned int b_mask= select, a_mask= ~b_mask;

    return (a&a_mask)|(b&b_mask);
}

int fast_int_max3(int a, int b, int c)
{
    return fast_int_max(a, fast_int_max(b, c));
}

Ответ 6

Булевозначные операторы (включая <, & &, и т.д.) обычно переводят на условные операции на уровне машинного кода, поэтому не соответствуют духу задачи. Здесь решение, которое любой разумный компилятор переводил бы только в арифметические инструкции без условных переходов (при условии, что long имеет больше битов, чем int, и этот длинный 64 бит). Идея заключается в том, что "m" захватывает и реплицирует знаковый бит b-a, поэтому m является либо всеми 1 битами (если a > b), либо всеми нулевыми битами (если a <= b). Обратите внимание, что длинный используется для предотвращения переполнения. Если по какой-то причине вы знаете, что b - a не перегружается/не работает, то использование long не требуется.

int max(int a, int b)
{
    long d = (long)b - (long)a;
    int m = (int)(d >> 63);
    return a & m | b & ~m;
}

int max(int a, int b, int c)
{
    long d;
    int m;
    d = (long)b - (long)a;
    m = (int)(d >> 63);
    a = a & m | b & ~m;
    d = (long)c - (long)a;
    m = (int)(d >> 63);
    return a & m | c & ~m;
}

Ответ 7

Нет условностей. Только актерский состав. Идеальное решение.

int abs (a) { return (int)((unsigned int)a); }
int max (a, b) { return (a + b + abs(a - b)) / 2; }
int min (a, b) { return (a + b - abs(a - b)) / 2; }


void sort (int & a, int & b, int & c)
{
   int max = max(max(a,b), c);
   int min = min(min(a,b), c);
   int middle = middle = a + b + c - max - min;
   a = max;
   b = middle;
   c = min;
}

Ответ 8

#include "stdafx.h"
#include <iostream>
int main()
{       
        int x,y,z;
        scanf("%d %d %d", &x,&y, &z);
        int max = ((x+y) + abs(x-y)) /2;
        max = ((max+z) + abs(max-z)) /2;
        printf("%d ", max);
        return 0;
}            

Ответ 9

Вы можете использовать этот код, чтобы найти самый большой из двух:

max{a,b} = abs(a-b)/2 + (a+b)/2

затем снова используйте его, чтобы найти третье число:

max{a,b,c} = max(a,max(b,c))

Посмотрите, что это работает для положительных чисел, которые вы можете изменить для работы и для отрицательных.

Ответ 10

Нет условные утверждения, просто циклы и назначения. И совершенно другая форма ответов других:)

while (a > b)
{
    while (a > c)
    {
        tmp = a;
        goto finish;
    }
    tmp = c;
    goto finish;
}
while (b > c)
{
    tmp = b;
    goto finish;
}
tmp = c;
finish: max = tmp;

Ответ 11

int compare(int a,int b, intc)
{
    return (a > b ? (a > c ? a : c) : (b > c ? b : c))
}

Ответ 12

Попробуйте это.

#include "stdio.h"
main() {
    int a,b,c,rmvivek,arni,csc; 
    printf("enter the three numbers");
    scanf("%d%d%d",&a,&b,&c);
    printf("the biggest value is %d",(a>b&&a>c?a:b>c?b:c));
}

Ответ 13

max =  a > b ? ( a > c ? a : c ) : ( b > c ? b : c ) ;