차이점

이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.

차이 보기로 연결

비트연산 [2011-12-24 17:33] (현재)
lifthrasiir 새로 만듦
줄 1: 줄 1:
 +====== 비트 연산 ======
  
 +여러 개의 [[비트]]로 이루어진 값(흔히 비트 갯수가 정해진 [[이진수]]일 때가 많다)을 다루기 위한 연산들.
 +
 +===== 비트별 연산 =====
 +
 +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언어]]에서 ''&^'' 이항 연산자로 지원한다.
 +? 비트 선택
 +! 특정 비트열에서 주어진 비트만 꺼내서 **순서대로** 나열하는 연산. 이 연산의 작동은 다음 그림으로 설명하는 것이 가장 빠르다: <code>
 +       1 0 1 0
 +select 1 0 0 1
 +--------------
 +       1     0 --> 1 0
 +</code> 이 연산은 비트 시프트의 일반화로 볼 수 있으나, 다른 비트 연산과는 달리 하드웨어에서 구현하는 경우가 별로 없어서 상당히 비싼 연산이다. [[INTERCAL]]에서 지원하는 몇 안 되는 연산 중 하나이며, [[MMIX]]가 이와 굉장히 유사한 명령(''SADD'')을 지원한다.
 +? 비트 확장
 +! 특정 비트열을 주어진 비트 위치에 재배치하는 연산. 비트 선택의 정 반대로 생각할 수 있으며, 마찬가지 이유로 상당히 비싼 연산이다. INTERCAL의 mingle 연산이 이 연산의 제약된 버전이다(''a $ b == (a expand ...1010) | (b expand ...0101)'').
 +? 비트 뒤집기
 +! Bit reversal. <del>[[밥상뒤집기]]</del> 말 그대로 비트열의 순서를 완전히 뒤집는 것. 매우 비싼 연산이자 매우 활용도가 높은 연산으로, [[빠른푸리에변환]](FFT)의 구현에 중요한 역할을 한다. 자세한 내용은 [[비트뒤집기]]를 참고.
 +? 해밍 무게
 +! Hamming weight 또는 population count. 주어진 비트열 안의 1 비트의 숫자를 가리킨다. 비트 뒤집기와 더불어 매우 비싼 연산이자 매우 활용도가 높은 연산으로, 자세한 내용은 [[해밍무게]]를 참고.
 +
 +===== 같이 보기 =====
 +
 +  * 《[[해커의즐거움]]》 (기초적인 내용을 담은 2장이 웹사이트에 [[http://hackersdelight.org/basics.pdf|공개]]되어 있다)
 +
 +===== 바깥 링크 =====
 +
 +  * [[http://rigaux.org/language-study/syntax-across-languages/Mthmt.html#MthmtBtwsprtr|각종 프로그래밍 언어의 비트 연산 문법들]]
 +
 +{{tag>프로그래밍}}

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