[20210605] Shift operator(>> & >>>) in java

5 Jun 2021 ~ 5 Jun 2021

java에서 shift 연산으로 >> 와 >>> 가 존재하는데, 이 둘의 차이점에 대해 공부한다.

java에서 정수형 변수 int는 4byte이다. 고로 int는 32bit로 표현된다. 물론 int뿐만 아니라 모든 것이 컴퓨터에서는 bit로 표현된다. 하지만, shift 연산은 정수형 변수에만 사용 가능하다.
그러면 shift 연산이 무엇이냐.

int x = 4; // 00000000 00000000 00000000 00000100

4는 비트로 표현하면 00000000 00000000 00000000 00000100 와 같다.
x « 2 는 x의 비트표현에서 왼쪽으로 2칸씩 모두 옮기라는 뜻이다.

x << 2; // 00000000 00000000 00000000 00010000

즉, 왼쪽으로 2칸씩 옮기게되면 00000000 00000000 00000000 00010000가 된다. 비트 32자리 중에 밀리는 최상위 비트 2개는 제거되고 최하위 비트 2개는 0으로 새로 생성된다.

그렇다면 »와 >>>의 차이는 무엇일까? 전체적인 알고리즘은 유사하다.
보통 » 를 arithmetic shift라 하고, >>> 를 logical shift라 한다. 이 차이는 정수형 변수가 음수일 때 발견할 수 있다.

int x = -4; // 11111111 11111111 11111111 11111100

java에서 음수는 2의 보수로 표현한다.

x >> 2; // 11111111 11111111 11111111 11111111
x >>> 2; // 00111111 11111111 11111111 11111111

차이를 보면, » 는 새로 만들어지는 비트를 최상위 비트와 같은 비트를 만드는 반면, >>> 는 항상 새로 만들어지는 비트를 0으로 한다. 그래서 음수에 >>>를 적용하면 양수가 만들어진다.

이진 탐색 코드 중에,

int mid = (low + high) / 2;

해당 코드를 본적 있을 것이다. 이는 low와 high의 중간값을 구하는 코드이다.
만약,

int low = 2000000000;
int high = 2100000000;
int mid = (low + high) / 2;

라면, mid의 예상 값은 2050000000 일것이다. 하지만, 해당 코드는 예상과 다르게 overflow가 발생해서 음수값이 나온다.
하지만,

int mid = (low + high) >>> 1;

>>>를 활용하면 low와 high가 높은 양수 값을 가지더라도 overflow가 발생하는 오류는 발생하지 않는다.

Table of Contents