Boolean Algebra

개요

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

Bit-level Operation

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)를 출력한다

A	B	A&B
0	0	0
0	1	0
1	0	0
1	1	1

OR(|)

두 명제 중 어느 한 명제만 참이어도 참값을 돌려준다.

A	B	A|B
0	0	0
0	1	1
1	0	1
1	1	1

NOT(~)

말 그대로 부정(否定)이다. 즉, 참과 거짓을 뒤집는다.

A	~A
0	1
1	0

베타적 논리합, XOR(^)

두 명제 중 정확히 하나만 참이어야, 혹은 두 명제의 참거짓 여부가 다를 때 참값을 돌려준다.

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

여담

C에서 피연산자들은 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 }