비트 연산

여러 개의 비트로 이루어진 값(흔히 비트 갯수가 정해진 이진수일 때가 많다)을 다루기 위한 연산들.

비트별 연산

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 비트의 숫자를 가리킨다. 비트 뒤집기와 더불어 매우 비싼 연산이자 매우 활용도가 높은 연산으로, 자세한 내용은 해밍무게를 참고.

같이 보기

바깥 링크


도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-12-24 17:33 | 작성자 lifthrasiir