비트 연산

bitwise operation

고정된 길이의 비트열 형태로 주어지는 자료형에 대해, 비트 단위로 값을 조작하는 연산.

1의 보수기와 비슷하게 CPU에서는 ALU에서 구현되어 있다.

이항연산의 경우 대부분 논리 연산에서 상속하며, 배타적 비트합 등은 프로그래밍 언어에 따라 별도 연산자로 지원하지 않는 경우도 있다. 대부분의 경우 비트합과 비트곱, 비트 부정의 합성으로 유도가 가능하기 때문.

값이 0 또는 1뿐인 진리집합과 달리 여러 비트의 벡터, 즉 비트열[1]을 원소로 가지기 때문에, 시프트와 순환이라는 특수한 연산이 존재한다.[2]

$\mathbb B_k$를 $k$개의 비트로 이루어진 비트열의 집합이라고 하자. 형식 언어론적으로 생각하면, $\Sigma=\{0,1\}$로 두었을 때 $\mathbb B_k=\Sigma^k$로 둘 수 있다. 편의상 $A\in\mathbb B_k$에 대해 $A_i$는 $A$의 $i$번째 비트를 뜻한다. 각 비트열 상수를 2진 정수로 해석한 결과는 볼드체로 표시한다. 예를 들어 $\mathbf 0=0^k$, $\mathbf 1=0^{k-1}\cdot 1$, $\mathbf{-1}=1^k$이다.

물론 꼭 형식 언어로만 표현할 필요는 없다. 조금 머리를 쓰면 순수하게 집합론적 언어만으로도 비트열군을 표현할 수 있는데, 임의의 길이 $k$짜리 비트열을 $\sum^{k-1}_{i=0}2^i$로 생각하고 이 $i<k$ 들의 집합을 생각할 수 있다. 그러면 모든 길이 $k$짜리 비트열의 집합 $\mathbb B_k$는 $\mathcal P(\{0,1,2,\dots,k-1\})$이 되고, 유한집합의 멱집합 크기를 생각하면 정확히 $|\mathbb B_k|=2^k$임을 알 수 있다. 비슷한 논리로 $\forall A,B\in\mathbb B_k$에 대해 비트 부정이 $\complement A$, 비트합이 $A\cup B$, 비트곱이 $A\cap B$, 배타적 비트합이 $(A\setminus B)\cup(B\setminus A)$, 좌측 순환이 $\{(i+n)\bmod k\mid i\in A\}$ 임 등을 쉽게 보일 수 있다. 본 문서는 계산 과정이 조금 더 직관적으로 와닿는 형식 언어적 표현을 우선한다.

bitwise not



bitwise complement, bitwise inversion 등으로도 불린다. 단항 연산으로, 주어진 비트열에 포함된 모든 비트를 뒤집는다.



기본적으로 동작 원리는 보수기와 동일하다. 형태는 $k$개의 비트에 대해 NOT 게이트를 병렬로 연결한 것. 후술할 다른 이항 연산들도 대부분 논리 연산에서 사용한 게이트를 병렬로 연결한 구조이다. 부호 있는(signed) 정수 표현에 2의 보수법을 쓰기 때문에, 1의 보수와 동치인 비트 부정의 결과는 원래 수의 부호를 반대로 한 것에서 1을 뺀 값이다. 즉 항상 $\overline{A}=-A-1$이다. 물론 상술했다시피 이는 부호 있는 자료형에서만 성립한다.

구체적인 연산자는 프로그래밍 언어에 따라 다르지만 주로 ~또는 !가 쓰이는 편. Go에서는 단항 ^X는 $\mathbf{-1}\oplus X=\overline{X}$로 평가되어 ^를 이항 xor에서도, 비트 반전에서도 사용할 수 있다. # Rust에서는 std::ops::Not trait의 일반화 때문에 비트 부정도 !를 사용한다.# Elixir에서는 ~~~을 사용한다.#

bitwise or



이항 연산으로, 합할 두 비트열에 주어진 각 비트를 순서대로 합한 것이 결과가 된다.



프로그래밍 언어에서는 주로 논리합 연산자로 ||를 사용하고, 비트합 연산자로 |를 사용한다.

bitwise and



마찬가지로 이항 연산으로, 곱할 두 비트열에 주어진 각 비트를 순서대로 곱한 것이 결과가 된다.



비트합과 마찬가지로 프로그래밍 언어에서는 주로 논리곱 연산자로 &&를 사용하고, 비트곱 연산자로 &를 사용한다. 비트 마스킹에 자주 쓰이는 연산.

bitwise xor



두 비트열의 각 비트에 대해 XOR 연산을 취하는 연산. 같은 위치의 두 비트의 값이 같을 경우 $0$, 다를 경우 $1$이 결과가 된다.



생각보다 활용도가 많은데, 비트군 위에서의 가역성 때문에 암호학이나 해시 구현, 때로는 간단한 swap hack 용도로도 사용된다.

프로그래밍 언어별로 표기가 난잡한 연산인데, 몇몇 언어에서는 별도 연산자가 할당되어 있지 않거나 표준 라이브러리의 함수로만 제공되기도 한다. 그나마 C family 언어는 대체로 ^으로 통일되어 있으나, 편의상 ^를 거듭제곱 연산자로 채택한 언어는 답이 없다. 일례로 ^를 거듭제곱 연산자로 사용하는# Lua는 단항 ~연산은 비트 부정으로, 이항 ~는 비트 xor로 사용한다.# 똑같이 거듭제곱으로 사용 중인 Julia는 한술 더 떠서 ⊻를 연산자(...)로 사용한다.# julia REPL에서 다른 TeX 기호처럼 \xor 입력 후 탭을 누르면 입력할 수 있지만 Haskell과 비슷하게 특이한 이항 연산자는 중위 표기법보다 함수형으로 쓰는 게 편하다.# C의 개발자 중 하나인 켄 톰슨에 따르면 XOR 연산자로 ^를 선택한 이유는 단지 아스키 문자 중 다른 연산자로 쓰이지 않고 남았던 문자들 중 아무거나 골랐던 것이라고.[3]

$\forall A\in\mathbb B_k$에 대해 $A\oplus A=\mathbf 0$이 되는데, 이는 XOR의 정의상 자기 자신과 같으면 0이 되기 때문이다. 이는 일종의 비트 수준에서의 != 연산과도 동치인데, 실제로 별도의 불리언 자료형이 없는 C언어에서는 ^를 != 대용으로도 쓸 수 있다. 이를 이용해 어셈블리에서는 빠르게 레지스터의 값을 0으로 비우기 위해 XOR ax, ax 등의 트릭을 사용하기도 한다.# 또한 $(\forall A\in\mathbb B_k)A+\mathbf 0=\mathbf 0+A=A$ 이기 때문에 자기 자신을 역원으로 가지게 된다. 이는 논리 연산과 마찬가지로 비트 연산 역시 불 격자를 이루기 때문으로, 이에 따라 불 대수의 많은 성질이 비트 연산에서도 보존된다.

위 성질들을 이용하면 흥미로운 결과를 볼 수 있는데, $A\oplus B$에 $A$를 XOR하면 $B$가 되고, $B$를 XOR하면 $A$가 나온다. C 코드로 표현하면

a = a ^ b
b = a ^ b
a = a ^ b

를 실행했을 때, a와 b 변수의 값이 서로 정확히 바뀌게 된다는 뜻이다. 이를 흔히 XOR swap이라고 부른다. XOR이 교환법칙과 결합법칙을 만족한다는 사실을 알고 있다면 증명은 간단하다. 우선 $A'=A\oplus B$, $B'=A'\oplus B$, $A''=A'\oplus B'$이라고 두자.



별로 의미없는 성질 같지만 이런 특징 때문에 대칭 열쇠 암호 알고리즘 구현에 중요하게 사용된다. 실제로도 비트 XOR 연산 한번만으로도 아주 간단한 비밀키 암호를 구현할 수 있다. 위 식에서 $A$를 암호화할 평문, $B$를 비밀키, $A\oplus B$를 암호문으로 바꿔서 생각하기만 하면 된다.

bitwise shift

비트를 일괄적으로 특정 방향으로 이동시키는 연산. 비트를 큰 방향(most significant)으로 옮기는지 작은 방향(least significant)으로 옮기는지에 따라 두 가지로 나뉜다. 일반적으로 값이 2의 거듭제곱 단위로 변화하지만, 음수의 경우 보통 MSB 방향에 부호 비트가 놓이므로 시프트 시 값이 2의 거듭제곱 단위가 되지 않을 수도 있다.

후술할 산술 시프트를 더욱 엄밀하게 구분하기 위해, 부호 비트를 무시하고 패딩을 항상 $0$으로 고정하는 시프트를 논리 시프트(logical shift)라고 하고 산술 시프트 종류에 좌측 산술 시프트를 추가하기도 한다. 다만 사실상 좌측 논리 시프트와 좌측 산술 시프트는 동치이기 때문에 큰 의미가 없다. 일반적으로 컴퓨터과학에서 시프트의 좌우 방향은 MSB 방향으로 결정되지, 인간이 인식하는 좌-우의 개념과는 사뭇 다르기 때문. 따라서 LSB 위치에 1을 복제하는 연산은 산술적으로도 논리적으로도 거의 아무 의미가 없다.



회로 수준에서는 위와 같은 barrel shifter로 구현된다. x86 어셈블리에서는 SHL, SHR로 사용할 수 있으며, 산술 시프트는 각각 SAL, SAR인데 SAL은 SHL과 정확히 같은 동작을 한다.#

C를 포함한 몇몇 언어에서 $n$이 음수이거나 $n\geq k$일 경우 undefined behavior이지만,[4] 수학적으로 의미 있게 정의하는 것 자체는 전혀 문제가 없기에 다른 언어에서는 $n\bmod k$로 적절히 처리하거나 음수일 경우 시프트 방향을 바꾸는 등으로 구현하기도 한다. 다만 CPU의 barrel shifter 구현이 이를 따라오지 못하는 경우가 많기 때문에 기계어를 별도로 추상화하지 않는 저수준 언어일수록 이런 제약에 엄격한 편. 이어지는 내용은 순수 수학적인 관점에서의 정의를 우선하며, $n<0$인 경우는 연산 방향을 바꾸는 것으로 해석한다.

C++와 같이 표준 입출력 연산자로 오버로딩 되어 있는 경우만 빼면 프로그래밍 언어에서는 주로 <<, >> 등의 겹부등호를 시프트 연산자로 사용한다.

shift left



주어진 길이 $n$만큼 비트를 앞으로 옮긴다. 이때 앞의 $n$개의 비트는 버려지고, 뒤에는 $0$이 $n$개 채워지게 된다.



지수법칙에 의해 일반적으로 $A\ll n=2^nA$이 성립함을 쉽게 알 수 있다. 2진 정수를 $A=2^0A_0+2^1A_1+\dots+2^{k-1}A_{k-1}=\sum^{k-1}_{i=0}2^iA_i$의 합 형태로 나타냈을 때 $n$칸 시프트를 수행하면 자릿수를 나타내는 $i$가 $n$만큼 증가한다고 생각할 수 있다. 따라서 $A\ll n=\sum^{k-1}_{i=0}2^{i+n}A_i$로 나타낼 수 있으며 분배법칙을 적용하면 $2^n\sum^{k-1}_{i=0}2^iA_i=2^nA$가 된다.

shift right



주어진 길이 $n$만큼 비트를 뒤로 옮긴다. 이때 뒤의 $n$개의 비트는 버려지고, 앞에는 무조건 $0$을 $n$개 채우게 된다. 부호 있는 정수의 경우 부호 비트까지 옮기고 그 자리를 0으로 채우므로 $n>0$에 대해 결과값은 모조건 양수가 된다.

Java나 JavaScript 등의 프로그래밍 언어에서는 경우에 따라 후술할 산술 시프트와의 구분을 위해 >를 하나 더 넣어 >>> 연산자를 사용하지만, 산술 시프트를 별도로 지원하지 않거나 타입에 따라 적절한 오버로딩을 하는 언어에서는 별도의 >>> 연산자가 없고 산술 시프트와 연산자를 구분하지 않는다. 예를 들어 일반적인 C에서는 >> 연산자의 LHS에 오는 값의 타입에 따라 unsigned면 논리 시프트를, signed면 산술 시프트를 수행한다.

arithmetic shift



우측 산술 시프트(arithmetic shift right) 또는 부호 시프트(signed shift)라고도 한다. 먼저 주어진 길이 $n$만큼 비트를 뒤로 옮기고, 앞의 $n$개의 비트를 부호 비트의 값과 똑같이 채운다. 우측 논리 시프트와 다르게 음수에서도 2의 거듭제곱 증감 성질을 보존하는데, 이는 음수가 2의 보수법에서 양수를 비트 부정한 값에 1을 더한 값임을 떠올리면 직관적으로 이해할 수 있다.




산술 시프트의 또 다른 산술적 특징으로, 연산을 수행한 비트열을 2진 정수로 해석할 경우 비트열의 길이와 무관하게 값이 동일하다. 즉 길이 $k$의 비트열을 정수로 해석하는 단사함수 $f_k:\mathbb B_k\to\Z$가 있을 때 $\forall k,j$에 대해 $(\forall X\in\mathbb B_k\forall Y\in\mathbb B_j)f_k(X)=f_j(Y)\implies f_k(X\gg n)=f_j(Y\gg n)$가 음수에 대해서도 항상 성립한다. 반면에 우측 논리 시프트의 경우 피연산자가 음수일 경우, 겉보기에는 똑같은 식을 계산하더라도 자료형의 크기가 얼마냐에 따라 결과가 차이나게 된다. 예를 들어 -123 >>> 4는 자료형이 8비트일 경우 8이 되지만,[5] 16비트일 경우 4088이 된다.[6] 어째서 이름이 산술 시프트인지 알 수 있는 부분.

자료형 길이에 무관하게 일관적으로 동작하기에 수치 자료형의 길이를 신경쓰지 않거나 자동으로 조절하는(arbitrary-precision) 방식으로 구현된 몇몇 스크립트 언어 산술 시프트가 기본 동작이기도 하며, 정적 타입 시스템을 가진 언어 중 부호 정수와 부호 없는 정수 타입을 엄격하게 구분하는 언어 등에서는 자료형에 따라 연산자 오버로딩을 사용해 주어진 자료형에 적절한 연산을 자동으로 골라 수행하기도 한다.

bitwise rotate



shift와 달리 명칭이 다소 통일되어있지 않아, 맥락에 따라 circular shift, bitwise roll 등으로도 불린다. 시프트 연산과 비슷하게 $n$개의 비트를 방향에 맞게 이동시키지만, 남는 비트를 버리는 것이 아닌 반대쪽 방향에 추가시킨다. 비트열의 양쪽 끝이 붙어 있는 상태로 회전(rotate)한다고 떠올리면 이해하기 좋다. 이러한 $n$차 일대일대응은 시저 암호와도 비슷하다.

시저 암호가 적절한 역연산이 존재해 해독 가능하듯이, 순환 연산도 임의의 $n$차 순환 연산에 대해 항상 역연산이 존재하는데, 편의상 이를 시프트처럼 주로 방향으로 구분하게 된다. 따라서 크게 좌측 순환, 우측 순환의 두 종류가 존재하게 되지만, 수학적으로는 캐리 플래그를 고려하지 않았을 때 두 연산이 근본적으로 동치임을 보일 수 있다. 즉, 어떠한 좌측 순환으로 임의의 우측 순환과 동일한 결과를 낼 수 있고, 그 반대도 성립한다. 때문에 구현체나 언어에 따라 하나의 함수만 제공한 후, 음수를 넣으면 반대 방향으로 회전하도록 하는 식으로 방향을 별도로 구분하지 않는 경우도 많다.

시프트 연산과 달리 가역적인 연산이기 때문에 암호학에서 주로 사용된다. 실제로 AES 암호 구현을 보면 32비트 rotate가 수 차례 사용된다.

회로 수준에서의 구현은 시프트와 거의 유사하다. 다만 회전하는 방향에 따라 캐리 플래그(carry flag)의 값이 바뀌게 되며, 이를 포함할 경우 일반적인 단순 순환 구현을 rotate no-carry, 캐리 플래그를 건드리는 순환 구현을 rotate through carry로 지칭하게 된다. x86 명령어 집합에서는 각각 ROR, ROL로 구현되고, 내부적으로 carry를 수행한다.

시프트에 비해 수학적인 의미도 별로 없고, 비트 마스킹에도 영 도움이 안 되기 때문에 대부분의 프로그래밍 언어에서는 별도의 연산자로 지원하지는 않는다. 주로 어셈블리 명령어와 비슷한 ror, rol 등의 이름을 가진 표준 라이브러리 함수로 제공되는 편. 시프트나 타 비트 연산의 경우 비트 마스킹과 관련된 내용을 배우면서 소개하거나 적어도 해당 언어의 연산자를 소개하면서 한번쯤은 언급하고 넘어가는 편이지만, 순환 연산의 경우 상술한 이유들이 겹쳐 언급조차 되지 않아 어셈블리나 로우레벨에 익숙하지 않다면 해당 연산의 존재 자체를 모르는 개발자들도 많다.

부호에 따라 2의 거듭제곱 성질이 보존되는 시프트 연산과 다르게, 순환 연산의 경우 sign bit가 항상 정해진 값으로 채워지기 때문에 부호가 있는 자료형에서 수행하면 연산을 수행할 때마다 부호가 들쭉날쭉하게 변하게 된다. 해당 연산이 사용되는 맥락(암호학, 압축 알고리즘 등)상 피연산자가 정수보다는 opaque한 버퍼로써 다루어지기 때문에 부호 없는 정수를 주로 쓰는 편이나, 부호 있는 정수를 넣더라도 메모리 상 결과는 동일하다. 때문에 산술 순환, 논리 순환 등의 구분이 별도로 존재하지 않는다.

rotate left



주어진 $n$만큼 좌측 방향으로 비트를 $n$칸씩 옮긴다. 이 때 맨 앞을 넘긴 비트는 다시 맨 뒤로 보내 남는 공간을 채운다.



소프트웨어 수준에서 다른 비트 연산을 합성해 구현하는 것도 가능하다.

$A\circlearrowleft n=A\ll(n\bmod k)\lor A\ggg(k - n\bmod k)$

rotate right



주어진 $n$만큼 우측 방향으로 비트를 $n$칸씩 옮긴다. 이 때 맨 뒤를 넘긴 비트는 다시 맨 앞으로 보내 남는 공간을 채운다.



좌측 순환과 마찬가지로, 다른 비트 연산을 합성해 구현하는 것도 가능하다.

$A\circlearrowright n=A\ggg(n\bmod k)\lor A\ll(k - n\bmod k)$

언어 내장 연산자, 명령어, 함수, 표준 라이브러리 수준에서 지원되는 경우만 표시한다. 우측 시프트가 없다는 것은 '부호 있는 자료형에서 동작하는 우측 논리 시프트'가 별도로 존재하지 않는다는 의미이다.

프로그래밍 언어에 따라 bitwise NAND, NOR 등 괴이한(?) 연산자를 제공하는 경우도 간혹 있다. 일례로 Go에는 &^(AND NOT) 연산자가 있는데, 정적 타입 언어인 동시에 수치형 타입 추론 매커니즘이 독특한 언어라 이런 연산자가 자료형 크기에 따라 단순히 ^랑 &를 합성하는 것과는 다른 결과를 낼 수 있다.#