Boolean Algebra 문서 원본 보기

==개요==
True를 1로서, False를 0으로 나타내여 Boolean Algebra를 수행할 수 있다.

==Bit-level Operation==
[[파일:BitSequenceOp.png|오른쪽|500x500픽셀]]
Bit-level Operation은 두가지 중요한 특징을 가진다.
* 교환법칙(e.g., A & B = B & A)
* 결합법칙(e.g., A & (B & C) = (A & B) & C)
아래의 Bit-level Operation은 bit sequence에도 적용된다.

====AND(&)====
A와 B 값이 모두 참이면 1(true)을 출력하고 둘 중 하나의 값이라도 거짓이면 0(false)를 출력한다
{| class="wikitable"
!A
!B
!A&B
|-
|0
|0
|0
|-
|0
|1
|0
|-
|1
|0
|0
|-
|1
|1
|1
|}

====OR(|)====
두 명제 중 어느 한 명제만 참이어도 참값을 돌려준다.
{| class="wikitable"
!A
!B
!<nowiki>A|B</nowiki>
|-
|0
|0
|0
|-
|0
|1
|1
|-
|1
|0
|1
|-
|1
|1
|1
|}

====NOT(~)====
말 그대로 부정(否定)이다. 즉, 참과 거짓을 뒤집는다.
{| class="wikitable"
!A
!~A
|-
|0
|1
|-
|1
|0
|}

====베타적 논리합, XOR(^)====
두 명제 중 정확히 하나만 참이어야, 혹은 두 명제의 참거짓 여부가 다를 때 참값을 돌려준다.
{| class="wikitable"
!A
!B
!A^B
|-
|0
|0
|0
|-
|0
|1
|1
|-
|1
|0
|1
|-
|1
|1
|0
|}

==Logical Operation==
Bit-level Operation과는 구분되지만 연산 방식은 거의 비슷하며 &&, ||, ! 연산자를 지원한다. 0를 False로, 그 외 나머지를 True로 간주하여 연산의 결과는 항상 0 혹은 1이 된다.
*예시
** !0x41 = 0x00
** !0x00 = 0x01
** 0x00 && 0x55 = 0x00
** 0x69 || 0x55 = 0x01

==Shift Operation==
* Left Shift(x << y): x의 최하위 bit 부분에 0을 y개 만큼 채운다. 즉, x * 2<sup>y</sup>와 동일한 연산이다.
** 다음은 x = 0b0011 일때 그 예시이며, 10진수로 해당 결과가 unsigned로 해석되었을 때, signed로 해석되었을 때 각각을 경우를 보여준다.
*** x << 1 = 0b0110 = 6<sub>10</sub> / 6<sub>10</sub>
*** x << 2 = 0b1100 = 12<sub>10</sub> / -4<sub>10</sub><ref>unsigned overflow</ref>
*** x << 3 = 0b1000 = 8<sub>10</sub><ref>signed overflow</ref> / -8<sub>10</sub>
* Right Shift(x >> y): x를 y bit만큼 오른쪽으로 민다. 두가지의 연산 방식이 존재한다.
** Logical Shift: x를 y bit만큼 오른쪽으로 민 만큼 빈 자리에 0을 채워넣는다. 즉, floor(x/2<sup>y</sup>)와 동일한 연산이다.
*** 보통 unsigned integer들에 사용된다.
*** 다음은 x = 0b1010 일때 그 예시이다. 
**** x >> 1 = 0b0101 = 5<sub>10</sub>
**** x >> 2 = 0b0010 = 2<sub>10</sub><ref>rounding</ref>
** Arithmetic Shift: x를 y bit만큼 오른쪽으로 민 만큼 빈 자리에 MSB와 같은 bit를 채워넣는다.
*** 보통 signed integer들에 사용된다.
*** 다음은 x = 0b1010 일때 그 예시이다. 
**** x >> 1 = 0b1101 = -3<sub>10</sub>
**** x >> 2 = 0b1110 = -2<sub>10</sub><ref>rounding</ref>

==여담==
C에서 피연산자<ref>long, int,short, char 자료형 변수</ref>들은 bit vector로 간주된다. 이런 피연산자들의 연산에 bit-level operation이 사용된다.

집합을 bit들을 통해서 표현할 수 있으며, bit-level operation을 통해서 집합의 교집합, 합집합, 여집합을 표현할 수 있다.
* bit로 집합 표현하기: 크기가 w인 bit vector는 {0, ..., w-1}의 부분집합을 나타낼 수 있다.
** X = { 0, 3, 5, 6 } is represented as 01101001 (why? 76543210)
** Y = { 0, 2, 4, 6 } is represented as 10010101 (why? 76543210)
* bit로 표현된 집합의 연산
** X & Y: Intersection / 01000001 / { 0, 6 }
** X | Y: Union / 01111101 / { 0, 2, 3, 4, 5, 6 }
** ~X: Complement / 10010110 / { 1, 2, 4, 7 }

==각주==



[[분류:컴퓨터 시스템]]