(Branchless Programming) 큰 값, 작은 값 고르기

큰 값

 

 

 

unbranched_max 함수의 작동 원리를 한번 살펴보자

b - ((b - a) &(b-a)>>31)); --> 이 부분에서 우리가 처음으로 봐야할 부분은

 

(b-a)>>31 이 부분이라고 할 수 있는데.

a > b 라면 (b-a) < 0 즉 음수

a < b 라면 (b-a) > 0 즉 양수

 

>> 31 는 비트를 모두 31만큼 오른쪽으로 옮겨 다음과 같은 결과를 낼 수 있다.

 

음수      -> -1 (0xFFFFFFFF)

양수, 0  -> 0

 

산술 시프트는 부호 시프트를 유지하면서 밀어내기 때문에 다음과 같이 된다.

 

int x = 5;        // 00000000 00000000 00000000 00000101
x >> 31 = 0;      // 00000000 00000000 00000000 00000000

 

int x = -5;       // 11111111 11111111 11111111 11111011
x >> 31 = -1;     // 11111111 11111111 11111111 11111111

 

 

다시 돌아가서  

b - ((b - a) &(b-a)>>31)); 

 

즉 쉬프트 연산 부분은 음수면 -1을 뱉고 양수면 0 을 뱉는다.

 

그럼 남은 연산은 (b-a) & -1 or (b-a) & 0 

비트앤드이기 때문에 

음수라면 ->(b-a) & -1          = b-a

양수, 0 이라면 -> (b-a) & 0  = 0

 

즉 a 가 b 보다 크다면  b - (b - a)  = a

b가 a 보다 크다면 b - 0 = b

 

조건문이 필요없이 단 한번의 연산으로 출력 가능하다.

 

 

작은 값

 

 

함수 이름을 바꾸지 않고 그대로 max 라 했지만 min 이라고 생각하자.

 

즉 max 함수와 논리는 똑같다 다만 식이 b- 대신 a + 로 바뀌었을 뿐

 

즉 a 가 b 보다 크다면  a + (b - a)  = b

b가 a 보다 크다면 a + 0 = a