| '''[[전기전자공학과|전기·전자공학 {{{#!wiki style="font-family: Times New Roman, serif; font-style: Italic; display: inline;"]]''' | |||
| {{{#!wiki style="margin:0 -10px -5px; min-height: 26px; word-break:keep-all" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin:-6px -1px -11px" | <colbgcolor=#009><colcolor=#fff> 학문 | 기반 학문 물리학 (전자기학 (회로이론 · 전자 회로 · 논리 회로) · 양자역학 · 물리화학 · 열역학 · 응집물질물리학) · 화학 연관 학문 수학 (공업수학 · 수치해석학 · 위상수학 · 미분방정식 · 대수학 (환론 · 표현론) · 선형대수학 · 이론 컴퓨터 과학 · 컴퓨터공학 (프로그래밍 언어 (HDL · VHDL · C · C++ · Java · 파이썬 · 베릴로그)) · 재료공학 · 제어 이론 | |
| 공식 · 법칙 | 전자기 유도 · 가우스 법칙 · 비오-사바르 법칙 · 무어의 법칙 · 키르히호프의 법칙 · 맥스웰 방정식 · 로런츠 힘 · 앙페르 법칙 · 드모르간 법칙 · 페르미 준위 · 중첩의 원리 | ||
| 이론 · 연구 | 반도체 (P형 반도체 · N형 반도체) · 디스플레이 · 논리 회로 (보수기 · 가산기 · 플립플롭 · 논리 연산 · 비트 연산) · 전자 회로 · RLC 회로 · 역률 · DSP · 히스테리시스 곡선 · 휘트스톤 브리지 · 임베디드 시스템 | ||
| 용어 | 클럭 · ASIC · CPU 관련 (BGA · 마이크로아키텍처 · GPS · C-DRX · 소켓) · 전계강도계 · 축전기 · CMCI · 전송선 · 양공 · 도핑 · 이미터 · 컬렉터 · 베이스 · 시퀀스 · 헤테로다인 | ||
| 전기 · 전자 관련 정보 | 제품 스마트폰 · CPU · GPU (그래픽 카드) · ROM · RAM · SSD · HDD · MPU · CCD · eMMC · USB · UFS · LCD · LED · OLED · AMOLED · IoT · 와이파이 · 스마트 홈 · 마그네트론 · 마이크 · 스피커 · 배터리 소자 집적 회로 · 다이오드 · 진공관 · 트랜지스터 (BJT · FET · JFET · MOSFET · T-FT) · CMOS · IGBT · 저항기 · 태양전지 · 연산 증폭기 · 사이리스터 · GTO · 레지스터 · 펠티어 소자 · 벅컨버터 | ||
| 자격증 | |||
| 전기 계열 | 기능사 전기기능사 · 철도전기신호기능사 기사 전기기사 · 전기산업기사 · 전기공사기사 · 전기공사산업기사 · 전기철도기사 · 전기철도산업기사 · 철도신호기사 · 철도신호산업기사 기능장 및 기술사 전기기능장 · 건축전기설비기술사 · 발송배전기술사 · 전기응용기술사 · 전기안전기술사 · 철도신호기술사 · 전기철도기술사 | ||
| 전자 계열 | 기능사 전자기기기능사 · 전자계산기기능사 · 전자캐드기능사 기사 전자기사 · 전자산업기사 · 전자계산기기사 · 기능장 및 기술사 전자기기기능장 · 전자응용기술사 | ||
| 기타 | 기능사 신재생에너지발전설비기능사(태양광) 기사 소방설비기사 · 신재생에너지발전설비기사(태양광) · 로봇소프트웨어개발기사 · 로봇하드웨어개발기사 · 로봇기구개발기사 | }}}}}}}}} | |
| 프로그래밍 언어 문법 | |
| {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: 0 -10px -5px; word-break: keep-all" | 프로그래밍 언어 문법 C(포인터 · 구조체 · size_t) · C++(클래스 · 이름공간 · 상수 표현식 · 특성) · C# · Java · Python(함수 · 모듈) · Kotlin · MATLAB · SQL · PHP · JavaScript(표준 내장 객체) · Haskell(모나드) |
| 마크업 언어 문법 HTML · CSS | |
| 개념과 용어 함수(인라인 함수 · 고차 함수 · 콜백 함수 · 람다식) · 리터럴 · 문자열 · 상속 · 예외 · 조건문 · 반복문 · 비트 연산 · 참조에 의한 호출 · eval · 네임스페이스 · 호이스팅 | |
| 기타 #! · == · === · deprecated · NaN · null · undefined · 배커스-나우르 표기법 | }}}}}} |
| 프로그래밍 언어 목록 · 분류 · 문법 · 예제 |
1. 개요
bitwise operation바이트가 아닌, 비트 단위로 값을 조작하는 연산.
1의 보수기와 비슷하게 CPU에서는 ALU에서 구현되어 있다.
2. 종류
이항연산의 경우 대부분 논리 연산에서 상속하며, 배타적 비트합 등은 프로그래밍 언어에 따라 별도 연산자로 지원하지 않는 경우도 있다. 대부분의 경우 비트합과 비트곱, 비트 부정의 합성으로 유도가 가능하기 때문.값이 0 또는 1뿐인 진리집합과 달리 여러 비트의 벡터를 원소로 가지기 때문에, 시프트라는 특수한 연산이 존재한다.
[math(\mathbb B_k)]를 [math(k)]개의 비트로 이루어진 비트열의 집합이라고 하자. 형식 언어론적으로 생각하면, [math(\Sigma=\{0,1\})]로 두었을 때 [math(\mathbb B_k=\Sigma^k)]로 둘 수 있다. 편의상 [math(A\in\mathbb B_k)]에 대해 [math(A_i)]는 [math(A)]의 [math(i)]번째 비트를 뜻한다. 각 비트열 상수를 2진 정수로 해석한 결과는 볼드체로 표시한다. 예를 들어 [math(\mathbf 0=0^k)], [math(\mathbf 1=0^{k-1}\cdot 1)], [math(\mathbf{-1}=1^k)]이다.
2.1. 비트 부정
bitwise not,~[math(\overline{A}=\overline{A_0}\cdot\overline{A_1}\cdot\overline{A_2}\dots\overline{A_k}\quad(\overline{A})_i=\overline{A_i})]
단항 연산으로, 주어진 비트열에 포함된 모든 비트를 뒤집는다. 기본적으로 동작 원리는 보수기와 동일하다. 구체적인 연산자는 프로그래밍 언어에 따라 다르지만 주로
~또는 !가 쓰이는 편. Go에서는 단항 ^X는 [math(\mathbf{-1}\oplus X=\overline{X})]로 평가되어 ^를 이항 xor에서도, 비트 반전에서도 사용할 수 있다. # Rust에서는 std::ops::Not trait의 일반화 때문에 비트 부정도 !를 사용한다.# Elixir에서는 ---을 사용한다.#2.2. 비트합
bitwise or,|[math(A\lor B=A_0\lor B_0\cdot A_1\lor B_1\cdot A_2\lor B_2\dots A_k\lor B_k\quad(A\lor B)_i=A_i\lor B_i)]
이항 연산으로, 합할 두 비트열에 주어진 각 비트를 순서대로 합한 것이 결과가 된다. 프로그래밍 언어에서는 주로 논리합 연산자로
||를 사용하고, 비트합 연산자로 |를 사용한다.2.3. 비트곱
bitwise and,&[math(A\land B=A_0\land B_0\cdot A_1\land B_1\cdot A_2\land B_2\dots A_k\land B_k\quad(A\land B)_i=A_i\land B_i)]
마찬가지로 이항 연산으로, 곱할 두 비트열에 주어진 각 비트를 순서대로 곱한 것이 결과가 된다. 비트합과 마찬가지로 프로그래밍 언어에서는 주로 논리곱 연산자로
&&를 사용하고, 비트곱 연산자로 &를 사용한다. 비트 마스킹에 자주 쓰이는 연산.2.4. 배타적 비트합
bitwise xor,^[math(A\oplus B=A_0\oplus B_0\cdot A_1\oplus B_1\cdot A_2\oplus B_2\dots A_k\oplus B_k\quad(A\oplus B)_i=A_i\oplus B_i)]
두 비트열의 각 비트에 대해 XOR 연산을 취하는 연산. 생각보다 활용도가 많은데, 비트군 위에서의 가역성 때문에 암호학이나 해시 구현, 때로는 간단한 swap hack 용도로도 사용된다.
프로그래밍 언어별로 표기가 난잡한 연산인데, 몇몇 언어에서는 별도 연산자가 할당되어 있지 않거나 표준 라이브러리의 함수로만 제공되기도 한다. 그나마 C family 언어는 대체로
^로 통일되어 있으나, 편의상 ^를 거듭제곱 연산자로 채택한 언어는 답이 없다. 일례로 ^를 거듭제곱 연산자로 사용하는# Lua는 단항 ~연산은 비트 부정으로, 이항 ~는 비트 xor로 사용한다.# 똑같이 거듭제곱으로 사용 중인 Julia는 한술 더 떠서 ⊻를 연산자(...)로 사용한다.# julia REPL에서 다른 TeX 기호처럼 \xor 입력 후 탭을 누르면 입력할 수 있지만 Haskell과 비슷하게 특이한 이항 연산자는 중위 표기법보다 함수형으로 쓰는 게 편하다.#[math(\forall A\in\mathbb B_k)]에 대해 [math(A\oplus A=\mathbf 0)]이 되는데, 이는 XOR의 정의상 자기 자신과 같으면 0이 되기 때문이다. 이는 일종의 비트 수준에서의
!= 연산과도 동치인데, 실제로 별도의 불리언 자료형이 없는 C언어에서는 ^를 != 대용으로도 쓸 수 있다. 또한 [math((\forall A\in\mathbb B_k)A+\mathbf 0=\mathbf 0+A=A)] 이기 때문에 자기 자신을 역원으로 가지게 된다. 이는 논리 연산이 환을 이루고 비트 연산으로 가는 준동형 사상이 있기 때문이다.위 성질들을 이용하면 흥미로운 결과를 볼 수 있는데, [math(A\oplus B)]에 [math(A)]를 XOR하면 [math(B)]가 되고, [math(B)]를 XOR하면 [math(A)]가 나온다. C 코드로 표현하면
#!syntax cpp
a = a ^ b
b = a ^ b
a = a ^ ba와 b 변수의 값이 서로 정확히 바뀌게 된다는 뜻이다. 이를 흔히 XOR swap이라고 부른다. XOR이 교환법칙과 결합법칙을 만족한다는 사실을 알고 있다면 증명은 간단하다. 우선 [math(A'=A\oplus B)], [math(B'=A'\oplus B)], [math(A''=A'\oplus B')]이라고 두자.[math(\begin{array}{ll}
B'&=A'\oplus B=(A\oplus B)\oplus B=A\oplus(B\oplus B)=A\oplus\mathbf 0=A\\
A''&=A'\oplus B'=(A\oplus B)\oplus A=(B\oplus A)\oplus A=B\oplus(A\oplus A)=B\oplus\mathbf 0=B\\
\end{array})]
B'&=A'\oplus B=(A\oplus B)\oplus B=A\oplus(B\oplus B)=A\oplus\mathbf 0=A\\
A''&=A'\oplus B'=(A\oplus B)\oplus A=(B\oplus A)\oplus A=B\oplus(A\oplus A)=B\oplus\mathbf 0=B\\
\end{array})]
별로 의미없는 성질 같지만 이런 특징 때문에 대칭 열쇠 암호 알고리즘 구현에 중요하게 사용된다. 실제로도 비트 XOR 연산 한번만으로도 아주 간단한 비밀키 암호를 구현할 수 있다. 위 식에서 [math(A)]를 암호화할 평문, [math(B)]를 비밀키, [math(A\oplus B)]를 암호문으로 바꿔서 생각하기만 하면 된다.
2.5. 시프트
bitwise shift비트를 일괄적으로 특정 방향으로 이동시키는 연산. 비트를 큰 방향(most significant)으로 옮기는지 작은 방향(least significant)으로 옮기는지에 따라 두 가지로 나뉜다. 일반적으로 값이 2의 거듭제곱 단위로 변화하지만, 음수의 경우 보통 MSB 방향에 부호 비트가 놓이므로 시프트 시 값이 2의 거듭제곱 단위가 되지 않을 수도 있다.
후술할 산술 시프트를 더욱 엄밀하게 구분하기 위해, 부호 비트를 무시하고 패딩을 항상 [math(0)]으로 고정하는 시프트를 논리 시프트(logical shift)라고 하고 산술 시프트 종류에 좌측 산술 시프트를 추가하기도 한다. 다만 사실상 좌측 논리 시프트와 좌측 산술 시프트는 동치이기 때문에 큰 의미가 없다. 일반적으로 컴퓨터과학에서 시프트의 좌우 방향은 MSB 방향으로 결정되지, 인간이 인식하는 좌-우의 개념과는 사뭇 다르기 때문. 따라서 LSB 위치에 1을 복제하는 연산은 산술적으로도 논리적으로도 거의 아무 의미가 없다.
회로 수준에서는 위와 같은 barrel shifter로 구현된다. x86 어셈블리에서는
SHL, SHR로 사용할 수 있으며, 산술 시프트는 각각 SAL, SAR인데 SAL은 SHL과 정확히 같은 동작을 한다.#C를 포함한 몇몇 언어에서 [math(n)]이 음수이거나 [math(n\geq k)]일 경우 undefined behavior[1]이지만, 수학적으로 의미 있게 정의하는 것 자체는 전혀 문제가 없기에 다른 언어에서는 [math(n\bmod k)]로 적절히 처리하거나 음수일 경우 시프트 방향을 바꾸는 등으로 구현하기도 한다. 다만 CPU의 barrel shifter 구현이 이를 따라오지 못하는 경우가 많기 때문에 네이티브로 컴파일되는 언어는 이런 제약에 엄격한 편. 이어지는 내용은 순수 수학적인 관점에서의 정의를 우선하며, [math(n<0)]인 경우는 연산 방향을 바꾸는 것으로 해석한다.
2.5.1. 좌측 시프트
shift left,<<[math(A\ll n=A_n\cdot A_{n+1}\cdot A_{n+2}\dots A_{k-1}\cdot 0^n\quad(A\ll n)_i=\begin{cases}A_{i+n}&(i\lt k-n)\\0&(i\geq k-n)\end{cases})]
주어진 길이 [math(n)]만큼 비트를 앞으로 옮긴다. 이때 앞의 [math(n)]개의 비트는 버려지고, 뒤에는 [math(0)]이 [math(n)]개 채워지게 된다. 지수법칙에 의해 일반적으로 [math(A\ll n=2^nA)]이 성립함을 쉽게 알 수 있다.
2.5.2. 우측 시프트
shift right,>>>[math(A\ggg n=0^n\cdot A_0\cdot A_1\cdot A_2\dots A_{k-n-1}\quad(A\ggg n)_i=\begin{cases}0&(i\lt n)\\A_{i-n}&(i\geq n)\end{cases})]
주어진 길이 [math(n)]만큼 비트를 뒤로 옮긴다. 이때 뒤의 [math(n)]개의 비트는 버려지고, 앞에는 무조건 [math(0)]을 [math(n)]개 채우게 된다. 부호 있는 정수의 경우 부호 비트까지 옮기고 그 자리를 0으로 채우므로 [math(n>0)]에 대해 결과값은 모조건 양수가 된다.
Java나 JavaScript 등의 프로그래밍 언어에서는 경우에 따라 후술할 산술 시프트와의 구분을 위해
>를 하나 더 넣어 >>> 연산자를 사용하지만, 산술 시프트를 별도로 지원하지 않거나 타입에 따라 적절한 오버로딩을 하는 언어에서는 별도의 >>> 연산자가 없고 산술 시프트와 연산자를 구분하지 않는다. 예를 들어 일반적인 C에서는 >> 연산자의 LHS에 오는 값의 타입에 따라 unsigned면 논리 시프트를, signed면 산술 시프트를 수행한다.2.5.2.1. 산술 시프트
arithmetic shift,>>[math(A\gg n=A_0^n\cdot A_0\cdot A_1\cdot A_2\dots A_{k-n-1}\quad(A\gg n)_i=\begin{cases}A_0&(i\lt n)\\A_{i-n}&(i\geq n)\end{cases})]
우측 산술 시프트(arithmetic shift right) 또는 부호 시프트(signed shift)라고도 한다. 먼저 주어진 길이 [math(n)]만큼 비트를 뒤로 옮기고, 앞의 [math(n)]개의 비트를 부호 비트의 값과 똑같이 채운다. 우측 논리 시프트와 다르게 음수에서도 2의 거듭제곱 증감 성질을 보존하는데, 이는 음수가 2의 보수법에서 양수를 논리 부정한 값에 1을 더한 값임을 떠올리면 직관적으로 이해할 수 있다.
2.6. 순환
bitwise rotate, circular shift시프트 연산과 비슷하게 [math(n)]개의 비트를 방향에 맞게 이동시키지만, 남는 비트를 버리는 것이 아닌 반대쪽 방향에 추가시킨다. 비트열의 양쪽 끝이 붙어 있는 상태로 회전(rotate)한다고 떠올리면 이해하기 좋다. 이러한 [math(n)]차 일대일대응은 시저 암호와도 비슷하다. 시저 암호가 적절한 역연산이 존재해 해독 가능하듯이, 순환 연산도 임의의 [math(n)]차 순환 연산에 대해 항상 역연산이 존재하는데, 편의상 이를 시프트처럼 주로 방향으로 구분하게 된다. 따라서 크게 좌측 순환, 우측 순환의 두 종류가 존재하게 되지만, 수학적으로는 캐리 플래그를 고려하지 않았을 때 두 연산이 근본적으로 동치임을 보일 수 있다. 즉, 어떠한 좌측 순환으로 임의의 우측 순환과 동일한 결과를 낼 수 있고, 그 반대도 성립한다.
시프트 연산과 달리 가역적인 연산이기 때문에 암호학에서 주로 사용된다. 실제로 AES 암호 구현을 보면 32비트 rotate가 수 차례 사용된다.
회로 수준에서의 구현은 시프트와 거의 유사하다. 다만 회전하는 방향에 따라 캐리 플래그(carry flag)의 값이 바뀌게 되며, 이를 포함할 경우 일반적인 단순 순환 구현을 rotate no-carry, 캐리 플래그를 건드리는 순환 구현을 rotate through carry로 지칭하게 된다. x86 명령어 집합에서는 각각
ROR, ROL로 구현되고, 내부적으로 carry를 수행한다.시프트에 비해 수학적 의미도 별로 없고, 비트 마스킹에도 영 도움이 안 되기 때문에 대부분의 프로그래밍 언어에서는 별도의 연산자로 지원하지는 않는다. 주로 어셈블리 명령어와 비슷한
ror, rol 등의 이름을 가진 표준 라이브러리 함수로 제공되는 편.2.6.1. 좌측 순환
rotate left[math(A\circlearrowleft n=A_n\cdot A_{n+1}\cdot A_{n+2}\dots A_{k-1}\cdot A_0\cdot A_1\dots A_{n-1}\quad(A\circlearrowleft n)_i=A_{i+(n\bmod k)})]
주어진 [math(n)]만큼 좌측 방향으로 비트를 [math(n)]칸씩 옮긴다. 이 때 맨 앞을 넘긴 비트는 다시 맨 뒤로 보내 남는 공간을 채운다.
2.6.2. 우측 순환
rotate right[math(A\circlearrowright n=A_{k-n}\cdot A_{k-n+1}\cdot A_{k-n+2}\dots A_{k-1}\cdot A_0\cdot A_1\dots A_{k-n-1}\quad(A\circlearrowright n)_i=A_{i-(n\bmod k)})]
주어진 [math(n)]만큼 우측 방향으로 비트를 [math(n)]칸씩 옮긴다. 이 때 맨 뒤를 넘긴 비트는 다시 맨 앞으로 보내 남는 공간을 채운다.
3. 관련 문서
[1] If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined. - C11 ISO/IEC 9899:201x p94-95