Intro

비트 연산이란 비트(bit) 단위의 논리 연산으로, 컴퓨터가 2진수를 사용하기 때문에 바이트 연산 대비 속도(시간복잡도 O(1))가 빠르고 메모리 사용(바이트의 8배) 역시 효율적이다.

다양한 곳에서 활용할 수 있지만, 특히 상태를 저장하고 관리할 때 상당히 효율적이기 때문에 알고리즘 문제 풀이에서 비트 마스킹에 비트 연산이 꼭 필요한 경우가 있다.

(그동안 이리저리 피해왔지만) 비트 연산자의 사용법과 알고리즘 문제 풀이에서 어떻게 사용되는지 알아보자

정의

코틀린은 중위 연산자 표기법을 지원하는 일반 함수를 사용해 비트 연산을 수행한다.

| 연산 | 왼쪽 시프트 | 오른쪽 시프트 (부호 비트 유지) | 오른쪽 시프트 (0으로 부호 비트 설정) | 비트 곱 | 비트 합 | 비트 배타 합 | 비트 반전 | | --- | --- | --- | --- | --- | --- | --- | --- | | Kotlin | shl | shr | ushr | and | or | xor | .inv() | | Java | << | >> | >>> | & | | | ^ | ~ |

사용법(코드)

각 연산자에 대해 어떻게 동작하고 알고리즘 문제에서 어떻게 활용하는지 확인해보자

먼저 결과를 확인하기 쉽게, Int의 10진수와 2진수 값을 출력해주는 확장 함수를 하나 선언한다.

fun Int.printBoth() { // 10진수 - 2진수 출력
    println("$this - ${this.toString(2)}")
}

shl (shift left)

비트를 왼쪽으로 한칸(2진수 기준) 이동 시킨다.

빈칸은 0으로 채워진다.

fun main() {
    val num = 1
    (num).printBoth()
    (num shl 1).printBoth()
    (num shl 2).printBoth()
    (num shl 3).printBoth()
}
// 출력

1  ==  1
2  ==  10
4  ==  100
8  ==  1000

활용

• 10진수의 2의 거듭 제곱 연산
• 비트 마스킹의 위치 결정

shr (shift right) / ushr (unsigned shift right)

비트를 오른쪽으로 한칸 이동 시킨다