비트 조작 (Bit Manipulation)

컴퓨터는 기계어 수준까지 내려가면 결국 모든 데이터를 0과 1처리합니다. 따라서 전산학에서는 오래 전부터 데이터를 일련의 비트로 다루는 능력을 중요시했었습니다.

현대 프로그래밍에서 비트 조작이 여전히 중요한지에 대해서는 분야마다 의견이 많이 갈리고 있지만, 적어도 코딩 테스트에서는 지원자가 비트 잘 다룰 수 있는지 시험하는 문제가 종종 나오기 때문에 준비가 필요합니다.

비트 연산자

코딩 테스트에서 비트 조작은 비트 연산자(Bitwise Operator)를 조합해서 이루어집니다. 그래서 각 이진 연산자의 특징을 정확하게 이해하는 것이 중요한데요.

~ 연산자는 부정(NOT)을 나타내며 0은 1로 바꾸고 1은 0로 바꿔서 반환합니다. 예를 들어, ~5은 ~0101이 되어 1010, 즉 10이 됩니다.

& 연산자는 논라곱(AND)을 나타내며 두 비트 중 하나라도 1이면 1을 반환합니다. 다시 말해서 두 비트가 모두 1일 때만 1을 반환합니다. 예를 들어, 5 & 3은 0101 & 0011이 되어 0001, 즉 1이 됩니다.

| 연산자는 논리합(OR)을 나타내며 두 비트가 모두 1일 때만 1을 반환합니다. 다시 말해서 두 비트가 모두 0일 때만 0을 반환합니다. 예를 들어, 5 & 3은 0101 | 0011이 되어 0111, 즉 7이 됩니다.

^ 연산자는 배타적 논리합(XOR)을 나타내며 두 비트가 서로 다를 때만 1을 반환합니다. 다시 말해서 두 비트가 동일할 때만 0을 반환합니다. 예를 들어, 5 ^ 3은 0101 ^ 0011이 되어 0110, 즉 6이 됩니다.

특히 ^ 연산자는 특히 코딩 테스트에서 중복값을 제거하거나 유일한 값을 찾을 때 활용할 수 있습니다. 두 개의 동일한 값을 ^ 연산자로 엮으면 0이 되기 때문입니다.

<< 연산자는 왼쪽 시프트를 나타내며 비트를 왼쪽으로 이동합니다. 예를 들어, 5 << 1은 0101 << 1이 되어 1010, 즉 10이 됩니다. x << y는 x * 2^y한 효과를 발휘해서 곱하기 대신에 사용하기도 합니다.

>> 연산자는 오른쪽 시프트를 나타내며 비트를 오른쪽으로 이동합니다. 예를 들어, 5 >> 1은 0101 >> 1이 되어 0010, 즉 2가 됩니다. x >> y는 x // 2^y한 효과를 발휘해서 나누기 대신에 사용하기도 합니다.

컴퓨터에서 어떻게 0과 1로 숫자를 표현할 수 있는지 알아보겠습니다.

간단하게 4비트로 표현할 수 있는 숫자를 생각해볼까요? 2의 4승을 하면 총 16개의 숫자를 표현할 수 있을텐데요.

양수를 0과 1로 표현하는 것은 딱히 어렵지 않은데요. 학창 시절 수학 시간에 이진수를 떠올리시면 될 것 같습니다.

음수를 0과 1로 표현하는 것은 살짝 더 어려울 수 있는데요. 보통 컴퓨터에서는 2의 보수(Two’s complement) 표현법을 사용하여 음수를 비트로 표현합니다.

음수 -x를 비트로 표현할 때는 먼저 x - 1의 비트를 구한 후에 비트를 반전(0은 1로, 1은 0으로 변경)시키면 됩니다. 수식으로 표현하면 -x = ~(x - 1)이 됩니다.

예를 들어, -3의 경우, 3 - 1, 즉 2의 비트는 0010이 되는데요. 이를 반전시키면 1101이 됩니다.

위 두개의 테이블 비교해보면 양수인 0부터 7의 최상위 비트는 0이고, 음수인 -8부터 -1의 최상위 비트는 1이라는 것을 알 수 있습니다. 따라서 2의 보수 표현법에서는 최상위 비트를 보고 양수인지 음수인지 판단할 수 있습니다.

이렇게 4비트로는 -8부터 7까지 숫자를 표현할 수 있습니다. 8비트로는 -129부터 128까지 숫자를 표현할 수 있을 것입니다.