여러 개의 비트로 이루어진 값(흔히 비트 갯수가 정해진 이진수일 때가 많다)을 다루기 위한 연산들.
Bitwise operation. 한국어에서는 비트"별" 연산과 비트 연산을 크게 구분하지 않는 것 같지만, 비트별 연산은 두 값에 대해서 대응되는 비트들끼리만 연산이 일어나고 위치가 같지 않아 대응되지 않는 비트들끼리는 연산이 일어나지 않는다는 점에서 비트 연산의 하위 개념이다.
여기에 속하는 연산들은 논리연산과 밀접한 관계를 맺고 있으며, 그 성질 또한 대응되는 논리 연산과 정확히 일치한다.
- 비트 NOT
- 논리부정에 대응되며, 흔히
~
나 ^
단항 연산자로 나타낸다. 2의보수 체계로 표현된 숫자의 경우, 어떤 수를 비트 NOT 한 결과는 해당 숫자의 부호를 바꾼 뒤 1을 뺀 것과 같다(C로 치자면 ~x == -x - 1
).
- 비트 AND
- 논리곱에 대응되며, 흔히
&
이항 연산자로 나타낸다. 크게 두 가지 사용 용도가 있다:
특정 비트가 설정되었는지 아닌지를 확인하려면, 확인할 비트만 설정된 숫자와 비트 AND를 해서 그 결과가 0이 아닌지 0인지 확인하면 된다. 이 때 확인할 비트만 설정된 숫자를 흔히 "비트 마스크"(bitmask)라 부른다.
특정 비트를 0으로 설정하고 다른 비트를 그대로 유지할 경우, 확인할 비트만 빼고 모든 비트가 설정된 숫자와 비트 AND를 하면 된다. 이 경우 비트 NOT과 함께 쓰이기도 한다.
- 비트 OR
- 논리합에 대응되며, 흔히
|
이항 연산자로 나타낸다. 특정 비트를 1로 설정하고 다른 비트를 그대로 유지할 때 쓰는데, 해당 비트만 설정된 숫자와 비트 OR을 하면 된다.
- 비트 XOR
- 배타적 논리합에 대응되며, 흔히
^
이항 연산자로 나타낸다. 특정 비트를 반전시키고 다른 비트를 그대로 유지할 때 쓰며(비트 OR과 같은 방법), 같은 숫자와 XOR을 두 번 하면 원래 숫자로 돌아 오기 때문에((x ^ y) ^ y == x
) XOR교환알고리즘이나 XOR연결리스트 등에서 사용하기도 한다.
Bit shift. 개별 비트는 그대로 유지한 채 그 위치만 수평으로 바꾸는 연산들을 일컫는다.
이 연산들은 흔히 "시프트할 비트 수"를 그 인자로 받는데, 왼쪽 또는 오른쪽으로 한 칸 움직이는 시프트를 그 횟수만큼 반복 수행하는 것으로 단항 연산자로 만들 수 있다. 이 경우 시프트를 한 뒤에 한 쪽 끝으로 삐져나간 비트는 사라지며, 대신 다른 한 쪽 끝에서 모자라는 비트를 어떻게 채울지를 가지고 연산자들을 분류할 수 있다.
- 산술 시프트
- Arithmetic shift. 오른쪽으로 시프트할 때는 원래 왼쪽 끝에 있던 비트를 왼쪽 빈 자리에 넣고, 왼쪽으로 시프트할 때는 오른쪽 끝에 0을 집어 넣는다. "산술" 시프트라 불리는 이유는 이 연산이 부호 있는 정수의 2로 나누기(오른쪽 시프트)나 2로 곱하기(왼쪽 시프트)와 연관이 있기 때문이다. (다만 1의보수 표현에서는 2로 나눌 때 절삭 방향이 약간 달라진다.) 흔히
<<
및 >>
이항 연산자로 나타내며, 연산자 오른쪽이 시프트할 비트 수를 가리킨다.
- 논리 시프트
- Logical shift. 오른쪽으로 시프트할 때나 왼쪽으로 시프트할 때나 빈 자리에 0을 집어 넣는다. 산술 시프트와 비슷하게, 이 연산은 부호 없는 정수의 2로 나누기나 2로 곱하기에 대응된다. 오른쪽 산술 시프트와 논리 시프트를 구분하는 언어의 경우 이 연산자는 흔히
>>>
로 쓰며, 구분하지 않을 경우 연산자 왼쪽이 부호가 있느냐 없느냐를 가지고 >>
의 동작을 바꾸는 게 일반적이다. (왼쪽 시프트는 산술이나 논리나 똑같으므로 다른 연산자가 필요하지 않다.)
- 비트 회전
- Bit rotation 또는 circular shift. 오른쪽으로 시프트할 때는 오른쪽으로 잘려 나간 비트를 왼쪽 빈 공간에 채우고, 왼쪽으로 시프트할 때는 왼쪽으로 잘려 나간 비트를 오른쪽 빈 공간에 채운다. 흔히 쓰이지는 않지만 모든 비트를 유지한 채 위치를 바꿀 때 종종 유용하며, 암호학에서 특히 많이 쓰인다.
- 자리 올림을 포함한 비트 회전
- 보통 비트 회전과 비슷하지만 원래 비트들과 별개로 자리 올림(carry) 비트가 회전에 관여하다는 점이 다르다. 산술 시프트와 논리 시프트를 이 연산만으로 구현할 수 있기 때문에 (예를 들어서 오른쪽 논리 시프트의 경우 자리 올림에 0을 넣으면 된다) 일부 프로세서에서는 시프트는 없고 회전 두 종류만 있는 경우도 있다.
아래 연산들은 흔히 나타나는 건 아니지만 종종 유용할 수도 있는(…) 그런 연산들이다.
- 비트 AND-NOT
- 비트 AND의 오른쪽 피연산자에 비트 NOT을 넣은 연산. Go언어에서
&^
이항 연산자로 지원한다.
- 비트 선택
- 특정 비트열에서 주어진 비트만 꺼내서 순서대로 나열하는 연산. 이 연산의 작동은 다음 그림으로 설명하는 것이 가장 빠르다:
1 0 1 0
select 1 0 0 1
--------------
1 0 --> 1 0
이 연산은 비트 시프트의 일반화로 볼 수 있으나, 다른 비트 연산과는 달리 하드웨어에서 구현하는 경우가 별로 없어서 상당히 비싼 연산이다. INTERCAL에서 지원하는 몇 안 되는 연산 중 하나이며, MMIX가 이와 굉장히 유사한 명령(SADD
)을 지원한다.
- 비트 확장
- 특정 비트열을 주어진 비트 위치에 재배치하는 연산. 비트 선택의 정 반대로 생각할 수 있으며, 마찬가지 이유로 상당히 비싼 연산이다. INTERCAL의 mingle 연산이 이 연산의 제약된 버전이다(
a $ b == (a expand …1010) | (b expand …0101)
).
- 비트 뒤집기
- Bit reversal.
밥상뒤집기 말 그대로 비트열의 순서를 완전히 뒤집는 것. 매우 비싼 연산이자 매우 활용도가 높은 연산으로, 빠른푸리에변환(FFT)의 구현에 중요한 역할을 한다. 자세한 내용은 비트뒤집기를 참고.
- 해밍 무게
- Hamming weight 또는 population count. 주어진 비트열 안의 1 비트의 숫자를 가리킨다. 비트 뒤집기와 더불어 매우 비싼 연산이자 매우 활용도가 높은 연산으로, 자세한 내용은 해밍무게를 참고.
《
해커의즐거움》 (기초적인 내용을 담은 2장이 웹사이트에
공개되어 있다)