if-else 또는 다른 비교 연산자를 사용하지 않고 최대 두 개의 정수를 찾는이 스 니펫을 설명 하시겠습니까?

if-else 또는 다른 비교 연산자를 사용하지 않고 최대 두 개의 정수를 찾는이 스 니펫을 설명 하시겠습니까?

---

최대 두 개의 숫자를 찾으십시오. if-else 또는 다른 비교 연산자를 사용하면 안됩니다. 온라인 게시판에서이 질문을 찾았으므로 StackOverflow에서 질문해야한다고 생각했습니다.

예제 입력 : 5, 10 출력 : 10

나는이 해결책을 찾았습니다. 누군가이 코드 줄을 이해하도록 도울 수 있습니까?

int getMax(int a, int b) {  
    int c = a - b;  
    int k = (c >> 31) & 0x1;  
    int max = a - k * c;  
    return max;  
}

---

int getMax(int a, int b) {
    int c = a - b;
    int k = (c >> 31) & 0x1;
    int max = a - k * c;
    return max;
}

이것을 해부합시다. 이 첫 번째 줄은 간단 해 보입니다 . a및 의 차이를 저장합니다 b. 이 값은 음수이고 a < b그렇지 않으면 음수가 아닙니다. 여기에 버그가 실제로있다 - 숫자의 차이가있는 경우 a와는 b죄송합니다 -이 정수에 맞지 않을 수 있도록 큰,이 정의되지 않은 동작으로 이어질 것입니다! 여기서는 그런 일이 발생하지 않는다고 가정 해 봅시다.

다음 줄에서

int k = (c >> 31) & 0x1;

아이디어는의 값 c이 음수 인지 확인하는 것입니다 . 거의 모든 현대 컴퓨터에서 숫자는 2의 보수 라는 형식으로 저장됩니다. 숫자 의 가장 높은 비트는 숫자가 양수이면 0이고 숫자가 음수이면 1입니다. 또한 대부분의 int는 32 비트입니다. (c >> 31)숫자를 31 비트 아래로 이동하여 숫자의 가장 높은 비트를 가장 낮은 비트에 남겨 둡니다. 이 숫자를 가져 와서 1 (마지막 비트를 제외한 모든 곳에서 이진 표현이 0 인 이진 표현)을 AND 처리하는 다음 단계는 모든 상위 비트를 지우고 가장 낮은 비트를 제공합니다. 의 가장 낮은 비트 c >> 31가의 가장 높은 비트이므로 c가장 높은 비트를 c0 또는 1로 읽습니다. 가장 높은 비트는 1이므로 iff c는 1이므로 다음 여부를 확인하는 방법입니다.c음수 (1) 또는 양수 (0)입니다. 이 추론을 위와 결합하면 k1이면 1이고 a < b그렇지 않으면 0입니다.

마지막 단계는 다음을 수행하는 것입니다.

int max = a - k * c;

만약 a < b, k == 1그리고 k * c = c = a - b, 그래서

a - k * c = a - (a - b) = a - a + b = b

어떤 때문에, 올바른 최대입니다 a < b. 그렇지 않은 경우 a >= b, 다음 k == 0과

a - k * c = a - 0 = a

또한 올바른 최대 값입니다.

---

여기 있습니다 : (a + b) / 2 + |a - b| / 2

---

비트 해킹 사용

r = x ^ ((x ^ y) & -(x < y)); // max(x, y)

알고 있다면 INT_MIN <= x - y <= INT_MAX,다음을 사용할 수 있습니다 (x - y). 한 번만 평가하면 되므로 더 빠릅니다 .

r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y)

출처 : Sean Eron Anderson의 Bit Twiddling Hacks

---

(sqrt( a*a + b*b - 2*a*b ) + a + b) / 2

이것은 mike.dld의 솔루션 과 동일한 기술을 기반으로 하지만 여기서 내가하는 일이 덜 "명백하지"않습니다. "abs"연산은 무언가의 부호를 비교하는 것처럼 보이지만 여기에서는 sqrt ()가 항상 양의 제곱근을 반환하므로 제곱 (ab)을 제곱 한 다음 제곱으로 작성합니다. 다시 응원하고 a + b를 더하고 2로 나눕니다.

예를 들어 10과 5의 사용자 예제에서는 sqrt (100 + 25-100) = 5를 얻은 다음 10을 더하고 5를 더하면 20을, 2로 나누면 10이됩니다.

9와 11을 숫자로 사용하면 (sqrt (121 + 81-198) + 11 + 9) / 2 = (sqrt (4) + 20) / 2 = 22/2 = 11

---

가장 간단한 대답은 다음과 같습니다.

#include <math.h>

int Max(int x, int y)
{
    return (float)(x + y) / 2.0 + abs((float)(x - y) / 2);
}

int Min(int x, int y)
{
    return (float)(x + y) / 2.0 - abs((float)(x - y) / 2);
}

---

int max(int i, int j) {
    int m = ((i-j) >> 31);
    return (m & j) + ((~m) & i);
}

이 솔루션은 곱셈을 방지합니다. m은 0x00000000 또는 0xffffffff입니다.

---

이동 아이디어를 사용하여 다른 사람이 게시 한 기호를 추출하는 다른 방법은 다음과 같습니다.

max (a, b) = new[] { a, b } [((a - b) >> 31) & 1]

이것은 인덱스가 두 숫자 사이의 차이의 부호 비트 인 배열 요소가 제공하는 최대 숫자를 가진 배열로 두 숫자를 밀어 넣습니다.

다음 사항에 유의하십시오.

1. 차이 (a - b)가 넘칠 수 있습니다.
2. 숫자에 부호가없고 >>연산자가 논리적 오른쪽 시프트를 참조하는 경우 & 1는 필요하지 않습니다.

---

내가 그 일을 어떻게 할 것이라고 생각하는지는 다음과 같습니다. 당신이 좋아하는 것만 큼 가독성이 좋지는 않지만, "X를하는 명백한 방법을 사용하지 않고 어떻게 X를 하는가?"로 시작할 때, 당신은 그것을 기대해야합니다. 이론적으로 이것은 약간의 이식성을 포기합니다. d 문제를보기 위해 매우 특이한 시스템을 찾아야합니다.

#define BITS (CHAR_BIT * sizeof(int) - 1)

int findmax(int a, int b) { 
    int rets[] = {a, b};
    return rets[unsigned(a-b)>>BITS];
}

이것은 질문에 표시된 것보다 몇 가지 장점이 있습니다. 우선, 32 비트 정수에 대해 하드 코딩되는 대신 올바른 시프트 크기를 계산합니다. 둘째, 대부분의 컴파일러에서 우리는 컴파일 타임에 모든 곱셈이 일어날 것으로 예상 할 수 있으므로 런타임에 남은 것은로드와 리턴이 뒤 따르는 사소한 비트 조작 (빼기와 시프트)뿐입니다. 요컨대, 이것은 가장 작은 마이크로 컨트롤러에서도 매우 빠르다는 것이 거의 확실합니다. 원래는 런타임에 발생해야하는 곱셈을 사용 했으므로 데스크톱 컴퓨터에서는 꽤 빠르지 만 종종 작은 마이크로 컨트롤러에서는 조금 느립니다.

---

그 라인이하는 일은 다음과 같습니다.

c는 ab입니다. c가 음수이면 a <b입니다.

k는 c의 부호 비트 인 c의 32 번째 비트입니다 (32 비트 정수라고 가정합니다. 64 비트 정수가있는 플랫폼에서 수행하면이 코드는 작동하지 않습니다). 가장 오른쪽에있는 31 비트를 제거하기 위해 오른쪽으로 31 비트 이동하고 가장 오른쪽에있는 부호 비트를 남겨두고 1로 이동하여 왼쪽에있는 모든 비트를 제거합니다 (c가 음수이면 1로 채워짐). 따라서 c가 음수이면 k는 1이되고 c가 양수이면 0이됩니다.

그러면 max = a-k * c. c가 0이면 a> = b를 의미하므로 max는 a-0 * c = a입니다. c가 1이면 a <b 다음 a-1 * c = a-(a-b) = a-a + b = b를 의미합니다.

전반적으로보다 크거나 작은 작업을 사용하지 않도록 차이의 부호 비트를 사용하고 있습니다. 이 코드가 비교를 사용하지 않는다고 말하는 것은 솔직히 약간 어리석은 일입니다. c는 a와 b를 비교 한 결과입니다. 코드는 비교 연산자를 사용하지 않습니다. 숫자를 빼고 상태 레지스터에 설정된 값을 기준으로 점프하여 많은 어셈블리 코드에서 비슷한 작업을 수행 할 수 있습니다.

또한이 모든 솔루션이 두 숫자가 정수라고 가정하고 있음을 추가해야합니다. 만약 그것들이 float, double, 또는 더 복잡한 것 (BigInts, Rational numbers 등)이라면 정말로 비교 연산자를 사용해야합니다. Bit-tricks는 일반적으로이를 위해하지 않습니다.

---

논리 연산이없는 getMax () 함수

int getMax(int a, int b){
    return (a+b+((a-b)>>sizeof(int)*8-1|1)*(a-b))/2;
}

---

설명:

'최대'를 조각으로 부수고

max
= ( max + max ) / 2
= ( max + (min+differenceOfMaxMin) ) / 2
= ( max + min + differenceOfMaxMin ) / 2
= ( max + min + | max - min | ) ) / 2

따라서 함수는 다음과 같아야합니다.

getMax(a, b)
= ( a + b + absolute(a - b) ) / 2

지금,

absolute(x)
= x [if 'x' is positive] or -x [if 'x' is negative]
= x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] )

정수 양수에서 첫 번째 비트 (부호 비트)는 -0입니다 . 음수는 -1 입니다. 비트를 오른쪽 (>>)으로 이동하여 첫 번째 비트를 캡처 할 수 있습니다.

오른쪽 시프트 동안 빈 공간은 부호 비트로 채워집니다. 따라서 01110001 >> 2 = 00011100 , 반면 10110001 >> 2 = 11101100 .

결과적으로 8 비트 숫자 시프 팅의 경우 7 비트는 음의 경우 1 1 1 1 1 1 [0 또는 1] , 양의 경우 0 0 0 0 0 0 0 [0 또는 1] 을 생성합니다.

이제 00000001 (= 1)으로 OR 연산을 수행 하면 음수는 11111111 (= -1) , 양수 -00000001 (= 1)이 됩니다.

그래서,

absolute(x)
= x * ( 1 [if 'x' is positive] or -1 [if 'x' is negative] )
= x * ( ( x >> (numberOfBitsInInteger-1) ) | 1 )
= x * ( ( x >> ((numberOfBytesInInteger*bitsInOneByte) - 1) ) | 1 )
= x * ( ( x >> ((sizeOf(int)*8) - 1) ) | 1 )

드디어,

getMax(a, b)
= ( a + b + absolute(a - b) ) / 2
= ( a + b + ((a-b) * ( ( (a-b) >> ((sizeOf(int)*8) - 1) ) | 1 )) ) / 2

---

또 다른 방법 -

int getMax(int a, int b){
    int i[] = {a, b};
    return i[( (i[0]-i[1]) >> (sizeof(int)*8 - 1) ) & 1 ];
}

---

static int mymax (int a, int b)

    {
        int[] arr;
        arr = new int[3];
        arr[0] = b;
        arr[1] = a;
        arr[2] = a;
        return arr[Math.Sign(a - b) + 1];

    }

b> a이면 (ab)가 음수이면 부호는 -1을 반환하고, 1을 더하면 b 인 인덱스 0을 얻고, b = a이면 ab는 0이고, +1은 1 인덱스를 제공하므로 중요하지 않습니다. a 또는 b를 반환하면 a> b이면 ab는 양수이고 sign은 1을 반환하고 1을 더하면 a가 저장된 인덱스 2가됩니다.

---

#include<stdio.h>
main()
{
        int num1,num2,diff;
        printf("Enter number 1 : ");
        scanf("%d",&num1);
        printf("Enter number 2 : ");
        scanf("%d",&num2);
        diff=num1-num2;
        num1=abs(diff);
        num2=num1+diff;
        if(num1==num2)
                printf("Both number are equal\n");
        else if(num2==0)
                printf("Num2 > Num1\n");
        else
                printf("Num1 > Num2\n");
}

---

내가 제공하는 코드는 두 숫자 사이의 최대 값을 찾기위한 것이며 숫자는 모든 데이터 유형 (정수, 부동) 일 수 있습니다. 입력 숫자가 같으면 함수는 숫자를 반환합니다.

double findmax(double a, double b)
{
    //find the difference of the two numbers
    double diff=a-b;
    double temp_diff=diff;
    int int_diff=temp_diff;
    /*
      For the floating point numbers the difference contains decimal
      values (for example 0.0009, 2.63 etc.) if the left side of '.' contains 0 then we need
      to get a non-zero number on the left side of '.'
    */
    while ( (!(int_diff|0)) && ((temp_diff-int_diff)||(0.0)) )
    {
       temp_diff = temp_diff * 10;
       int_diff = temp_diff;
    }
    /*
      shift the sign bit of variable 'int_diff' to the LSB position and find if it is 
      1(difference is -ve) or 0(difference is +ve) , then multiply it with the difference of
      the two numbers (variable 'diff') then subtract it with the variable a.
    */
    return a- (diff * ( int_diff >> (sizeof(int) * 8 - 1 ) & 1 ));
}

기술

• 함수가 가장 먼저 인수를 double로 취하고 반환 유형을 double로 사용합니다. 그 이유는 모든 유형에 대해 최대 값을 찾을 수있는 단일 함수를 생성하기 때문입니다. 정수 유형 숫자가 제공되거나 하나는 정수이고 다른 하나는 부동 소수점 인 경우 암시 적 변환으로 인해 함수를 사용하여 정수의 최대 값도 찾을 수 있습니다.
• 기본 논리는 간단합니다. ab> 0 (즉, 차이가 양수)이면 a와 b가 최대이고 ab == 0이면 둘 다 같고 ab <0 (즉, diff가- ve) b는 최대입니다.

• 부호 비트는 메모리에 MSB (Most Significant Bit)로 저장됩니다. MSB가 1이고 그 반대의 경우도 마찬가지입니다. MSB가 1인지 0인지 확인하기 위해 MSB를 LSB 위치로 이동하고 Bitwise & 1로 결과가 1이면 숫자는 -ve가 아니면 no입니다. + ve입니다. 이 결과는 다음 명령문으로 얻습니다.

  int_diff >> (sizeof (int) * 8-1) & 1

여기서 MSB에서 LSB로 부호 비트를 가져 오려면 오른쪽으로 k-1 비트로 이동합니다 (여기서 k는 시스템 유형에 따라 메모리에 정수를 저장하는 데 필요한 비트 수). 여기서 k = sizeof (int) * 8 as sizeof ()는 정수를 저장하는 데 필요한 바이트 수를 제공합니다. 비트 수에 8을 곱합니다. 오른쪽 시프트 후에 비트와 1을 적용하여 결과를 얻습니다.

• Now after obtaining the result(let us assume it as r) as 1(for -ve diff) and 0(for +ve diff) we multiply the result with the difference of the two numbers, the logic is given as follows:

  1. if a>b then a-b>0 i.e., is +ve so the result is 0(i.e., r=0). So a-(a-b)*r => a-(a-b)*0, which gives 'a' as the maximum.
  2. if a < b then a-b<0 i.e., is -ve so the result is 1(i.e., r=1). So a-(a-b)*r => a-(a-b)*1 => a-a+b =>b , which gives 'b' as the maximum.

• Now there are two remaining points 1. the use of while loop and 2. why I have used the variable 'int_diff' as an integer. To answer these properly we have to understand some points:

  1. Floating type values cannot be used as an operand for the bitwise operators.
  2. Due to above reason, we need to get the value in an integer value to get the sign of difference by using bitwise operators. These two points describe the need of variable 'int_diff' as integer type.
  3. Now let's say we find the difference in variable 'diff' now there are 3 possibilities for the values of 'diff' irrespective of the sign of these values. (a). |diff|>=1 , (b). 0<|diff|<1 , (c). |diff|==0.
  4. When we assign a double value to integer variable the decimal part is lost.
  5. For case(a) the value of 'int_diff' >0 (i.e.,1,2,...). For other two cases int_diff=0.
  6. The condition (temp_diff-int_diff)||0.0 checks if diff==0 so both numbers are equal.
  7. If diff!=0 then we check if int_diff|0 is true i.e., case(b) is true
  8. In the while loop, we try to get the value of int_diff as non-zero so that the value of int_diff also gets the sign of diff.

---

Here are a couple of bit-twiddling methods to get the max of two integral values:

Method 1

int max1(int a, int b) {
  static const size_t SIGN_BIT_SHIFT = sizeof(a) * 8 - 1;
  int mask = (a - b) >> SIGN_BIT_SHIFT;
  return (a & ~mask) | (b & mask);
}

Explanation:

• (a - b) >> SIGN_BIT_SHIFT - If a > b then a - b is positive, thus the sign bit is 0, and the mask is 0x00.00. Otherwise, a < b so a - b is negative, the sign bit is 1 and after shifting, we get a mask of 0xFF..FF
• (a & ~mask) - If the mask is 0xFF..FF, then ~mask is 0x00..00 and then this value is 0. Otherwise, ~mask is 0xFF..FF and the value is a
• (b & mask) - If the mask is 0xFF..FF, then this value is b. Otherwise, mask is 0x00..00 and the value is 0.

Finally:

• If a >= b then a - b is positive, we get max = a | 0 = a
• If a < b then a - b is negative, we get max = 0 | b = b

Method 2

int max2(int a, int b) {
  static const size_t SIGN_BIT_SHIFT = sizeof(a) * 8 - 1;
  int mask = (a - b) >> SIGN_BIT_SHIFT;
  return a ^ ((a ^ b) & mask);
}

Explanation:

• Mask explanation is the same as for Method 1. If a > b the mask is 0x00..00, otherwise the mask is 0xFF..FF
• If the mask is 0x00..00, then (a ^ b) & mask is 0x00..00
• If the mask is 0xFF..FF, then (a ^ b) & mask is a ^ b

Finally:

• If a >= b, we get a ^ 0x00..00 = a
• If a < b, we get a ^ a ^ b = b

---

//In C# you can use math library to perform min or max function

using System;

class NumberComparator {

static void Main()
{

    Console.Write(" write the first number to compare: ");
    double first_Number = double.Parse(Console.ReadLine());

    Console.Write(" write the second number to compare: ");
    double second_Number = double.Parse(Console.ReadLine());

    double compare_Numbers = Math.Max(first_Number, second_Number);
    Console.Write("{0} is greater",compare_Numbers);

}

}

---

The logic described in a problem can be explained as if 1st number is smaller then 0 will be subtracted else difference will be subtracted from 1st number to get 2nd number. I found one more mathematical solution which I think is bit simpler to understand this concept.

Considering a and b as given numbers

c=|a/b|+1;
d=(c-1)/b;
smallest number= a - d*(a-b);

Again,The idea is to find k which is wither 0 or 1 and multiply it with difference of two numbers.And finally this number should be subtracted from 1st number to yield the smaller of the two numbers. P.S. this solution will fail in case 2nd number is zero

---

int a=151;
int b=121;
int k=Math.abs(a-b);
int j= a+b;
double k1=(double)(k);
double j1= (double) (j);
double c=Math.ceil(k1/2) + Math.floor(j1/2);
int c1= (int) (c);
System.out.println(" Max value = " + c1);

---

There is one way

 public static int Min(int a, int b)
  {
   int dif = (int)(((uint)(a - b)) >> 31);
   return a * dif + b * (1 - dif);
  }

and one

return (a>=b)?b:a;

---

Guess we can just multiply the numbers with their bitwise comparisons eg:

int max=(a>b)*a+(a<=b)*b;

참고URL : https://stackoverflow.com/questions/4772780/explain-this-snippet-which-finds-the-maximum-of-two-integers-without-using-if-el