중간 값 구하는 여러가지 방법

백기선의 자바 스터디를 늦게라도 해보려고 천천히 공부하고 있다. 3주차 연산자 공부를 하는 도중에 중간값을 구하는 방법이 여러 가지 있어가지고 충격이었다. 한번도 이것이 문제가 될거라고 생각이 들지 않았기 때문이다. 

intMax1>= 0 ,intMax2 >=0인 두개의 수가 있다고 가정하자
문제점은 우리가 흔히 하는 방법인 (intMax1 + intMax2) / 2 이 방식이 문제가 있다는 것이다.  나는 너무나 당연하게 여태까지 이 방식으로 중간 값을 구하였다. 결론부터 말하면 intMax1와 intMax2가 자료형이 표현할수 있는 범위를 넘어서면 overflow가 발생해서 이상한 값이 나온다는 점이다. 

public class Main {

    public static void main(String[] args) {
        Integer intMax1 = Integer.MAX_VALUE;
        Integer intMax2 = Integer.MAX_VALUE;
        Integer sumIntMaxs = intMax1 + intMax2;
		Integer midValue = start + end/2;
        
        System.out.println("intMax1 : " + intMax1);
        System.out.println("intMax2 : " + intMax2);
        System.out.println("sumIntMaxs : " + sumIntMaxs);
        System.out.println("midValue : " + midValue);

        System.out.println("binary intMAx1 : "+ Integer.toBinaryString(intMax1));
        System.out.println("binary intMax2 : "+ Integer.toBinaryString(intMax2));
        System.out.println("binary sumIntMaxs : "+ Integer.toBinaryString(sumIntMaxs));        
    }
}

이 코드를 실행하면 아래와 같은 결과값이 나온다. 

intMax1 : 2147483647
intMax2 : 2147483647
sumIntMaxs : -2
midValue : -1073741826
binary intMAx1 :    0111 1111 1111 1111 1111 1111 1111 1111
binary intMax2 :    0111 1111 1111 1111 1111 1111 1111 1111
binary sumIntMaxs : 1111 1111 1111 1111 1111 1111 1111 1110
binary midValue :   1011 1111 1111 1111 1111 1111 1111 1110

 

여기서 보면 sumIntMaxs 값이 -2가 나온것을 확인할 수 있다. -2는 2의 보수를 십진수로 표현하였다. 

너무 비트수가 길어서 sumIntMaxs 2진수에서 4개의 비트로 계산을 하였다. 그랬더니 결과값이 -2가 나왔다. 
즉, 2,147,483,647 + 2,147,483,647  = 4,294,967,294 에서 1/2을 한다면 2,147,483,647값이 나와야하는데 이미 int 표현범위가 2,147,483,647까지라서 더이상 표현을 하지 못한 상태에서 나누기 2를 하게 된다. 그래서 엉뚱한 값이 나왔다. 

[해결방법1]
-> overflow가 나지 않도록 계산하는 방법 

중간값 구하는 방법1

 

 

 

이 방식을 사용한다면 overflow가 나는 현상을 막을수 있다. 왜냐하면 end-start/2를 하기 때문에 숫자 범위를 넘어가도록 하지 않는다. 그런데 이 식을 처음 보고서 어떻게 이게 중간값이지?? 라는 의문이 들었다. 그래서 이 식이랑 기존에 풀던 방식이랑 같은지 한번 식으로 증명해보았다. (수학을 잘 못해서 증명을 이렇게 해도 되는걸까 싶지만...) 

중간값 구하는 방법1 증명

결국 식을 그대로 계산 해보면 (start + end) / 2이 나온다. 결국에는 같은 식이지만 overflow가 나지 않도록 하는 계산 방식인것이다. 나도 이제 이런 방식으로 중간값을 구해야겠다. 사소한 버그 하나가 결과값이 다르게 나올수 있으니 말이다. 

[해결방법2]
-> 비트 연산자를 이용하는 방법

비트연산자를 이용하는 방법

>>> 비트연산자를 이용하는 것이다. >> 와 >>>의 차이점은 간단하게 말하면 자리 옮김으로 인한 채워지는 수가 부호비트로 채워지는지 아니면 무조건 0으로 채워지는지 차이이다. 

>> : 부호비트

>>> : 0

이런 차이점이 있다. 비트연산자에서 왼쪽으로 이동은 2배씩 늘어가지만 오른쪽으로 이동은 나누기 2가 된다. 이 원리를 이용해서 이진수로 먼저 표현을 하고서 오른쪽으로 이동한다면 중간값이 나올 것이다. 위에 보면 sumIntMaxs 값이 맨앞이 1이였지만 오른쪽으로 이동하면서 0으로 채워지고 맨 마지막 0은 버리게 된다. 따라서 결국에는 intMax1값과 동일하게 되어서 중간값이 되었다. 

public class Main {

    public static void main(String[] args) {
        Integer intMax1 = Integer.MAX_VALUE;
        Integer intMax2 = Integer.MAX_VALUE;
        Integer sumIntMaxs = intMax1 + intMax2;
        Integer midValue = sumIntMaxs >>> 1;

        System.out.println("intMax1 : " + intMax1);
        System.out.println("intMax2 : " + intMax2);
        System.out.println("sumIntMaxs : " + sumIntMaxs);
        System.out.println("midValue : " + midValue);

        System.out.println("binary intMAx1 : "+ Integer.toBinaryString(intMax1));
        System.out.println("binary intMax2 : "+ Integer.toBinaryString(intMax2));
        System.out.println("binary sumIntMaxs : "+ Integer.toBinaryString(sumIntMaxs));
        System.out.println("binary midValue : "+ Integer.toBinaryString(midValue));

    }
}

 

intMax1 : 2147483647
intMax2 : 2147483647
sumIntMaxs : -2
midValue : 2147483647
binary intMAx1 : 1111111111111111111111111111111
binary intMax2 : 1111111111111111111111111111111
binary sumIntMaxs : 11111111111111111111111111111110
binary midValue : 1111111111111111111111111111111

백기선님은 이 방식을 사용하면 폼나게 중간값이 나온다고 설명하였는데...나도 폼나게 중간값 구할때는 이 방식으로 사용해야겠다. 이상으로 블로그 글을 마치겠다.