중간값을 구하는 안전한 방법

보통 중간값을 다음과 같이 나타내는 경우가 많은데,

int mid = (start + end) / 2;

이건 별로 좋은 방법이 아니다. 작은 수에서는 문제가 일어나지 않지만 start + end가 정수 표현 범위(-2,147,483,647 ~ 2,147,483,647)를 넘어서는 경우 오버플로우가 일어나기 때문에 원하는 값을 얻을 수 없다.

 

public class Main {

    public static void main(String[] args) {

        int start = 1_500_000_000;
        int end = 1_600_000_000;
        int mid = (start + end) / 2;
        System.out.println("mid = " + mid);
    }

}

실행 결과

mid = -597483648

 

따라서 중간값은 다음과 같이 표현하는 것이 안전하다.

int mid = start + (end - start) / 2;

이렇게 하면 start와 end가 정수 범위 내에 있는 이상 중간값을 구하는 과정에서 오버플로우가 일어날 일이 없다.

 

비트쉬프트를 이용할 수도 있다.

int mid = (start + end) >>> 1;

정수 비트열을 오른쪽으로 한 칸 이동하는 것은 2로 나누는 것과 같기 때문에 첫 번째 예시와 의미적으로 같다. 하지만 (start + end)가 21억을 넘어서 최상단 비트(MSB)가 1이 되더라도 비트를 오른쪽으로 이동하기 때문에 오버플로우가 일어나지 않는다.

  1,500,000,000 (0101 1001 ... 0000 0000)
+ 1,600,000,000 (0101 1111 ... 0000 0000)  // 덧셈
--------------------------------------------
- 597,483,648   (1011 1000 ... 0000 0000)  // 원래라면 MSB가 1이 되기 때문에(오버플로우) 음수 값이 나옴
>>> 1                                      // 오른쪽으로 한 비트씩 자리옮김
--------------------------------------------
1,550,000,000   (0101 1100 ... 0000 0000)  // 원하던 중간값이 도출됨

이 방법은 우아하긴 하지만 다른 사람들이 이해하기 어려울 수도 있고, 양수 범위에서만 사용할 수 있기 때문에 일반적으로는 첫 번째 방법을 쓰는 것이 낫다.