Java로 알아보는 비트 연산과 시프트 연산

이번 글에서는 잘 사용하면 복잡한 연산을 쉽고 빠르게 처리할 수 있는 비트 연산과 시프트 연산을 알아보고 Java로 실습해 보겠습니다.

 

비트 연산

`비트 연산(bitwise operation)`은 이진수에 대해 비트 단위로 적용되는 연산입니다. 비트 연산자에는 논리 연산에서 사용되는 논리합(OR), 논리곱(AND), 배타적 논리곱(XOR), 부정(NOT)이 있습니다. 많은 프로그래밍 언어에서 `비트 연산자`로 &(AND), |(OR), ^(XOR), ~(NOT)을 사용합니다. `비트 연산의 진리표`는 논리 연산의 진리표에서 True와 False를 1과 0으로 바꾸면 됩니다. 진리표는 아래와 같습니다.

AND(&)		OR(|)		XOR(^)		NOT(~)
1 & 1	1	1 | 1	1	1 ^ 1	0	~1	0
1 & 0	0	1 | 0	1	1 ^ 0	1	~0	1
0 & 1	0	0 | 1	1	0 ^ 1	1
0 & 0	0	0 | 0	0	0 ^ 0	0

 

시프트 연산

`시프트 연산(bit shift operation)`은 피연산자의 비트를 옮기는 연산입니다. 시프트 연산에는 `산술 시프트(arithmetic shift)`와 `논리 시프트(logical shift)`가 있습니다. 

산술 시프트는 산술성을 보존하기 위해 부호를 유지합니다. 따라서 `signed shift`라고도 합니다. 논리 시프트는 시프트의 논리적인 의미대로 부호와 상관없이 비트를 옮깁니다. 논리 시프트는 `unsigned shift`라고도 합니다. 자바에는 `시프트 연산자(shift operator)` `<<`(left shift), `>>`(signed right shift), `>>>`(unsigned right shift)가 있습니다. 시프트 연산은 예시로 설명드리겠습니다.

- Left Shift

left shift는 모든 비트를 왼쪽으로 옮기고 빈 곳은 0으로 채웁니다. 연산자는 `<<`입니다. 의미적으로는 2의 거듭제곱을 곱하는 것과 같습니다. 십진수 27로 예를 들어보겠습니다. 편의상 8비트 Byte자료형으로 표현하겠습니다.

System.out.println(Integer.toBinaryString(27).substring(24));  // 00011011 = 27
System.out.println((byte)(27<<1)); // 00110110 = 54 = 27 * 2^1
System.out.println((byte)(27<<2)); // 01101100 = 108 = 27 * 2^2
System.out.println((byte)(27<<3)); // 11011000 = -40
System.out.println((byte)(27<<5)); // 01100000 = 96
System.out.println((byte)(27<<6)); // 11000000 = -64
System.out.println((byte)(27<<7)); // 10000000 = -128
System.out.println((byte)(27<<8)); // 00000000 = 0

27은 이진수로 11011이고 byte자료형은 8비트이니 빈자리는 0으로 채워진 00011011입니다. 27 << 1을 실행하면 11011이 왼쪽으로 한 칸이 밀리면서 범위를 벗어난 왼쪽값은 사라지고 가장 오른쪽 비트는 0으로 채워집니다. 따라서 00110110인 54가 결과로 출력됩니다. 이는 27에 2를 곱한 값과 같습니다.

- Signed Right Shift

signed right shift는 비트를 오른쪽으로 옮기고 빈 곳은 sign bit로 채웁니다. 연산자는 `>>`입니다. 의미적으로는 부호를 유지하며 2로 나누는 것과 같습니다. 27과 -27으로 예를 들어 보겠습니다.

System.out.println(Integer.toBinaryString(27).substring(24)); // 00011011 = 27
System.out.println((byte)(27>>1)); // 00001101 = 13
System.out.println((byte)(27>>2)); // 00000110 = 6
System.out.println((byte)(27>>3)); // 00000011 = 3
System.out.println((byte)(27>>4)); // 00000001 = 1
System.out.println((byte)(27>>5)); // 00000000 = 0
System.out.println((byte)(27>>6)); // 00000000 = 0

System.out.println(Integer.toBinaryString(-27).substring(24)); // 11100101 = -27
System.out.println((byte)(-27>>1)); // 11110010 = -14
System.out.println((byte)(-27>>2)); // 11111001 = -7
System.out.println((byte)(-27>>3)); // 11111100 = -4
System.out.println((byte)(-27>>4)); // 11111110 = -2
System.out.println((byte)(-27>>5)); // 11111111 = -1
System.out.println((byte)(-27>>6)); // 11111111 = -1

- Unsigned Rigth Shift

unsigned rigth shift는 비트를 오른쪽으로 옮기고 빈 곳은 0으로 채웁니다. 연산자는 `>>>`입니다. 빈 곳을 0으로 채우기 때문에 연산결과는 항상 양수입니다. 양수의 경우 signed rigth shift와 결과가 같으니 음수의 경우만 살펴보겠습니다.

System.out.println(Integer.toBinaryString(-27).substring(24));    // 11100101 = 27
System.out.println((byte)((-27 & 0xff)>>>1)); // 01110010 = 114
System.out.println((byte)((-27 & 0xff)>>>2)); // 00111001 = 57
System.out.println((byte)((-27 & 0xff)>>>3)); // 00011100 = 28
System.out.println((byte)((-27 & 0xff)>>>4)); // 00001110 = 14
System.out.println((byte)((-27 & 0xff)>>>5)); // 00000111 = 7
System.out.println((byte)((-27 & 0xff)>>>6)); // 00000011 = 3
System.out.println((byte)((-27 & 0xff)>>>7)); // 00000001 = 1
System.out.println((byte)((-27 & 0xff)>>>8)); // 00000000 = 0
System.out.println((byte)((-27 & 0xff)>>>9)); // 00000000 = 0

-27 대신 (-27 & 0xff)를 사용한 이유는 정수의 기본 자료형은 integer로 리터럴 -27은 integer형이기 때문입니다. 또 연산자의 기본 자료형 또한 integer이기 때문에 byte 타입의 변수를 시프트 연산을 하게 되면 자동으로 integer로 형변환되어 연산됩니다. 따라서 integer타입에서 끝 8개의 비트를 제외한 나머지 비트를 0으로 만든 뒤 integer로 연산하고 byte로 캐스팅했습니다.

		-27				= 11111111111111111111111111100101
		-27 >>> 1		= 11111111111111111111111111110010
(byte)(	-27 >>> 1)		= 11110010 // -14

		 -27					= 11111111111111111111111111100101
		(-27 & 0xff)			= 00000000000000000000000011100101
		(-27 & 0xff) >>> 1		= 00000000000000000000000001110010
(byte)(	(-27 & 0xff) >>> 1)		= 01110010 // 114

 

응용

비트 연산과 시프트 연산을 어떻게 사용할 수 있는지 살펴보겠습니다.

- 음수

양수 a가 있을 때, -a는 a의 2의 보수와 같습니다. 또 2의 보수는 1의 보수에 1을 더한 값과 같습니다.

• ~a: a의 1의 보수
• ~a+1: a의 2의 보수

27로 예를 들면 -27은 (~27+1)로 계산할 수 있습니다.

 a   = 27  // 00011011
~a   = -28 // 11100100
~a+1 = -27 // 11100101

- 비트 수 세기

Java 에는 Integer.bitCount 함수가 있지만 bitCount를 비트 연산자를 이용해 만들 수 있습니다.

int bitCount(int n){
    int count=0;
    while(n>0){
        n &= n-1;
        count++;
    }
    return count;
}

- 코딩테스트

코딩테스트에 주로 사용되는 비트 연산과 시프트 연산을 살펴보겠습니다.

// 30개 비트가 모두 1인 숫자 만들기
(1<<30) - 1;

// 특정 위치(p)를 1로 만들기
x |= (1<<p);
// 특정 위치를 0으로 만들기
x &= ~(1<<p);

// 특정 위치가 1인지 확인하기
if( (x&(1<<p)) == 1 )
// 특정 위치가 0인지 확인하기
if( (x&(1<<p)) == 0 )

// 특정 위치 토글
x ^= 1<<p // XOR 연산은 x^0은 그대로 x^1은 토글

added = a | b // 비트 합집합
intersection = a & b // 비트 교집합
removed = a & (~b) // 비트 차집합 a-b = a and (~b)
toggled = a ^ b // a나 b중 한 곳에만 1이 있는

// 처음으로 등장하는 0 찾기
x^(x+1) // if x=11010111 => 00001111 (처음 등장하는 0의 자릿수 부터 끝까지 1)

 

비트연산을 익히기 좋은 문제들을 모아봤습니다.

[프로그래머스] 2개 이하로 다른 비트

[프로그래머스] 다음 큰 숫자

[소프티어] 전광판