조건문과 3항 연산자를 사용하지 않고 C에서 최대 3개의 숫자 찾기

조건문과 3항 연산자를 사용하지 않고 C에서 최대 3개의 숫자 찾기

저는 사용자가 제공하는 최대 3개의 번호를 찾아야 하지만 몇 가지 제한이 있습니다.조건문은 사용할 수 없습니다.아래와 같이 ternary operator를 사용해 보았습니다.

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

하지만 역시 삼원 연산자를 사용하는 것은 제한적입니다.이제 어떻게 하는지 전혀 모르겠어요?

부울 식에서 단락의 이점 활용:

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)false입니다. 그러면 두 번째 하위 표현식은 평가되지 않습니다.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

구현을 기록합니다.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;
}

효과는 이제 부울 식을 에 캐스팅한다는 것이며, 이는 경고를 억제하는 원인이 됩니다.

정수를 다룬다고 가정하면 다음은 어떻습니까?

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

조건부 실행을 피하기 위한 또 다른 대안을 추가하는 것입니다(사용할 수 있는 대안은 아니지만 솔루션 집합에서 누락된 것처럼 보임).

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, lookup array의 첫 번째 인덱스에 신중하게 저장됩니다.만약 그 표현이 거짓이 된다면, 우리는 다시 돌아옵니다.a요소로 저장된0Lookup Array의.이를 구성 요소로 사용하면 다음과 같이 말할 수 있습니다.

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).

---

(이 부분은 결론에 도달하기 전에 측정해야 하는 또 다른 증거일 뿐입니다. 마지막 편집 참조)

제가 실제로 사용할 수 있는 것은...아마도 @FooBaa의 것은 매크로가 아닌 인라인 함수를 사용하도록 수정되었을 것입니다.다음 옵션은 이 옵션 또는 @MSN의 옵션 중 하나입니다.

수용된 답변에 존재하지 않는 이 세 가지 해결책의 공통분모는 그것들이 단지 다음의 통사적 구조를 피하지 않는다는 것입니다.if또는 3항 연산자.?:, 하지만 분기를 아예 피하게 되고 성능에 영향을 미칠 수 있습니다.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명령(인텔 x64 플랫폼에서 g++로 테스트 수행):

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

조건부 이동 지침에 따라 분기 가능성을 피할 수 있습니다.

다른 솔루션들 중 어떤 것도 분기점을 가지고 있지 않지만, 그들 모두는 이것보다 더 많은 CPU 명령어로 번역되며, 결국 우리는 항상 간단한 코드를 작성하고 컴파일러가 우리를 위해 그것을 최적화하도록 해야 한다고 안심시킵니다.

업데이트: 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에서는 보이지 않습니다.)

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));
}

부울 값 연산자(<, & & 등 포함)는 일반적으로 기계 코드 수준의 조건부 연산으로 변환되므로 도전 정신을 수행하지 마십시오.여기 합리적인 컴파일러가 조건부 점프 없이 산술 명령어로만 번역하는 솔루션이 있습니다(길이가 int보다 비트 수가 많고 길이가 64비트라고 가정하면).아이디어는 "m"이 b - a의 부호 비트를 캡처하여 복제한다는 것입니다. som은 모든 1비트(a > b인 경우) 또는 모든 0비트(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;
}

조건 없음.깁스만 한 거죠.완벽한 해결책.

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;
}

이 코드를 사용하여 두 가지 중에서 가장 큰 것을 찾을 수 있습니다.

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

그런 다음 이 값을 다시 사용하여 세 번째 숫자를 찾습니다.

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

양수의 경우에도 적용되므로 음수의 경우에도 적용되도록 변경할 수 있습니다.

#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;
}            

조건문은 없고 루프와 과제만 있습니다.그리고 다른 사람들의 대답과는 전혀 다른 것 :)

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;

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

이거 먹어봐요.

#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));
}

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

언급URL : https://stackoverflow.com/questions/7074010/find-maximum-of-three-number-in-c-without-using-conditional-statement-and-ternar