- int[] 에서 특정 정수와 일치하는 값이 있는지 확인하는 코드를 짜다가 Arrays.binarySearch를 봄
- 이진 탐색 알고리즘은 대충 알고 있어서 java 안에서 어떻게 구현되어 있는지 들여다 봄
private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1; // >>는 알고 있었는데 >>> 이것은 또 무엇인가...
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
- 비트 이동 연산자는 <<와 >>만 있는 줄 알았는데 >>>가 있었음!
- 음수를 비트 이동 연산할때 >>는 부호 비트를 유지하고, >>>는 그딴거 신경 안쓰고 0으로 채운다고 함
2의 보수표현법부터...
8 : 00000000 00000000 00000000 00001000
-8 : 11111111 11111111 11111111 11111000 // 모든 비트 역전 후 1을 더함
32비트 시스템에서의 >>와 >>>의 차이 (ex. -8>>1 vs -8>>>1)
- case ">>"
11111111 ... 11111000 >> 11111111 ... 11111100 : 결과 -4
- case ">>>"
11111111 ... 11111000 >>> 01111111 ... 11111100 : 결과 2,147,483,644
유의사항 : 비트 연산은 정수 타입 기준(32비트)으로 변경하여 수행
- byte 타입으로 같은 연산을 수행하면 이렇게 되겠지?
11111000 >> 11111100 : -4
11111000 >>> 01111100 : 60
- 노노 이렇게임 (IDE에서 알아서 (byte)로 형변환하라고 알려줌)
11111111 ... 11111000 >> 11111111 ... 11111100 : 결과 -4
11111111 ... 11111000 >>> 01111111 ... 11111100 : 결과 -4 -> (byte)로 마지막 8비트만 가져옴
- 이건 그럼 왜 만들게 되었는가?
- 이진 탐색에서 mid pointer를 만들 때 high가 MAX_VALUE이면 low를 더했을 때 문제가 생김
int high = Integer.MAX_VALUE;
int low = 1;
여기서 mid를 구해보자.
case 1. 인간 (계산기x, 엑셀x) -> 1,073,741,824
case 2. (high + low) / 2 -> -1,073,741,824
case 3. (high + low) >> 1 -> -1,073,741,824
case 4. (high + low) >>> 1 -> 1,073,741,824
이진수로 한 번 보자. // 아놔 줄 좀..
Integer의 MAX_VALUE = 2,147,483,647 -> 01111111 11111111 11111111 11111111
여기서 1을 더하면 -2,147,483,648 -> 10000000 00000000 00000000 00000000
/2 나 >> 1 을 하면 -1,073,741,824 -> 11000000 00000000 00000000 00000000
>>> 1 을 하면!!! 1,073,741,824 -> 01000000 00000000 00000000 00000000 // 짜잔~