Bitwise operation I

Bitwise operation

 

일반적으로 프로그램 하는 사람들이 의외로 비트단위(Bitwise)의 연산을 모르는 경우가 많더군요.  실제 테스트 삼아서 몇 가지 문제를 내면, 못 맞추는 경우가 많아서 의아해했습니다.  실무 영역에서는 많이 사용되고 있는데, 실제 그것을 이용해서 프로그램 짜는 경우는 드물어 보입니다.

 

우리가 부울 변수 x, y를 입력으로 어떤 함수를 작성한다면, 총 16가지의 함수를 만들 수가 있습니다.  이 함수들은 논리 함수(Logical function)라고 이야기를 하며, 교환법칙이 성립하는 경우는 총 8가지가 존재합니다.  이 8가지 중 2가지는 상수 함수이므로, 실제 우리가 사용하는 논리 함수는 6가지 뿐입니다.  상당히 적죠.

 

이것을 표로 작성하면 다음과 같습니다.

 

x, y	0, 0	0, 1	1, 0	1, 1
OR	0	1	1	1
AND	0	0	0	1
XOR	0	1	1	0
XAND	1	0	0	1
NOR	1	0	0	0
NAND	1	1	1	0

 

이렇게 6가지 함수들은 잘 보면 세가지 함수(OR, AND, XOR)와 나머지 세가지 함수(XAND, NOR, NAND)는 서로 반대 함수인 것을 알 수 있습니다.  즉 세가지 함수와 단항 함수인 NOT 함수를 이용해서 우리는 필요한 논리 연산을 할 수 있습니다.

 

비트단위 연산은 이 논리 연산을 비트 단위로 적용하는 것입니다.  예를 들어서 비트 단위 연산자 AND 연산자를 x 이라고 규정한다면, 다음과 같이 표현할 수 있습니다.

 

\[ 1011011_2 \times 0110010_2 = 0010010_2 \]

 

즉, 각 비트(당연히 2진수로 표현하면 각 자리 숫자는 하나의 비트겠죠.)마다 AND 연산을 한 것이라고 생각할 수 있습니다.

 

비트 단위 연산은 위에서 이야기한 OR, AND, XOR 그리고 NOT이 있습니다.  이것을 C 언어에서는 각각 |, &, ^, ~ 로 표기하고 있습니다.  여기서도 편의상 C 언어 표기법을 따르도록 하겠습니다.

 

앞서 이야기했듯이 교환법칙만 성립하는 연산자를 골랐기 때문에 특별하게 교환법칙, 그리고 결합법칙에 대해서는 이야기할 필요는 없겠죠.  알아두면 편리한 공식들에 대해서 간단하게 나열해볼께요.

 

(x | y) &z = (x &z) | (y &z)       (x &y) | z = (x | z) &(y | z)

(x ^ y) &z = (x &z) ^ (y &z)      (x &y ) | x = x     (x | y) &x = x

 

다음으로는 우리가 비트 단위 연산을 정의할 때, 한정된 비트를 사용하지 않고, 일반화된 무한 비트를 사용토록 합니다.  이것은 우리가 앞으로 식을 정리할 때, 보다 일반화할 수 있습니다.

 

\[ (…000)_2 = 0 ~~~~~ (…111)_2 = -1 \]

 

즉 무한한 수로 표현할 수 있으며, -1 = ~0 이라고 표기할 수 있습니다.  자 이것과 관련해서 우리는 또 몇가지 공식을 더 정의할 수 있습니다.

 

x &0 = 0    x | -1 = -1

x &-1 = x   x | 0 = x

x ^ 0 = x     x ^ -1 = ~x

 

이것까지 이해했다면, 이제 많은 부분을 이해한 것입니다.  그러면 이제 음수 표현법에 대해서 정의하고자 합니다.  -1 이라는 음수가 이미 나왔으므로, 우리는 음수 표현법에 대해 다음과 같이 정의합니다.

 

-x = ~x + 1 = ~(x-1)

 

이제 비트 단위 연산은 덧셈, 뺄셈의 영역까지 오게 됩니다.  실제 많은 경우의 비트 연산에서는 덧셈, 뺄셈, 곱셈, 나눗셈 영역으로 확장되며, 결국 우리가 사용하는 컴퓨터가 비트 단위 연산을 기본으로 하고 있으며, 이를 이용해서 사칙연산을 지원하게 됩니다.  그리고 비트 연산은 가장 빠른 연산입니다.

 

비트 단위 연산자 중 두 개의 연산자를 더 정의코자 합니다.  바로 <<, >>입니다.  이 연산자는 비트를 왼쪽 또는 오른쪽으로 이동시켜줍니다.

 

\[ (…0001)_2 \lt \lt 2 = (…0100)_2 \]

 

형태로 우리는 비트를 옮겨줄 수 있습니다.  이 연산자 역시 매우 중요한 역할을 합니다.

 

\[ x \lt \lt k = x \gt \gt –k \]

\[ x \lt \lt k = x \times 2^k \]

\[ x \gt \gt k = x \div 2^k \]

 

첫 번째 식은 쉽게 이해를 할 수 있는 부분이지만, 두 번째, 세 번째는 선뜻 이해를 못 합니다.  이것을 쉽게 설명하고자 할 때, 저는 이런 문제를 냅니다.  3276 곱하기 100 은 얼마일까요?  이것에 대한 답은 산수를 조금 공부한 사람이라면 쉽게 답합니다.  왜일까요?  바로 3276 뒤에 0을 두 개 붙이면 된다는 것을 알고 있기 때문입니다.  100은 10의 제곱이기 때문입니다.  2진수에서 바로 이러한 수는 2의 멱승수입니다.  식(2)와 식(3)은 그런 원리로 이해하시면 됩니다.

 

이와 비슷하게 우리는 나머지 연산자인 %로 표시할 수 있는 유용한 것들이 있습니다.  바로 AND 연산자입니다.

 

x % \(2^k\) = x & (\(2^k – 1\))

 

이 식도 앞과 마찬가지로 이해하면 편할 것입니다.  5421을 100으로 나눈 나머지는 얼마일까요?  마찬가지로 우리는 나누기를 하지 않아도 손쉽게 답을 찾을 수 있겠죠.