algorithm

Question 1

최대 두 개의 숫자를 찾으십시오. 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;
}

Question 2

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

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

Question 3

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

Question 4

비트 해킹 사용

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

Question 5

(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

Question 6

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

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

Question 7

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

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

Question 8

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

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

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

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

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

algorithm

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

답변

답변

답변

답변

답변

답변

답변