[시스템프로그래밍] Data Representation - Boolean Algebra, Integer Representation

 

데이터 표현: 불 대수와 정수 표현

오늘은 불 대수(Boolean Algebra)와 정수 데이터 표현(Integer Representation)에 대해 다뤄보고자 한다. 흔히 간과하기 쉬운 이 개념들은, 사실 우리가 매일 사용하는 소프트웨어와 하드웨어의 동작 방식을 이해하는 데 필수적인 초석이 된다. Low-level에서 이러한 원리들을 탐구하며, 컴퓨터 과학적 사고 능력을 한 단계 끌어올리는 것을 목표로 한다.

1. 디지털 논리의 심장: 불 대수와 비트 연산

지난 시간 알아본 바에 의하면, 컴퓨터는 결국 0과 1이라는 이진수 체계 위에서 작동하는 기계이다. 이러한 이진 논리의 근간을 이루는 것이 바로 불 대수(Boolean Algebra)이다. 불 대수는 참(True, 1)과 거짓(False, 0) 두 가지 값과, 이를 조작하는 기본적인 논리 연산들로 구성된다.

기본적인 불 연산:

• AND (논리곱, &): 두 입력이 모두 1일 때만 결과가 1이 된다. 마치 "그리고"라는 접속사처럼, A와 B가 모두 참이어야 참인 명제와 같다.
• OR (논리합, |): 두 입력 중 하나라도 1이면 결과가 1이 된다. "또는"과 유사하게, A 또는 B 둘 중 하나 이상이 참이면 참이다.
• NOT (논리 부정, ~): 입력을 반전시키는 연산이다. 0은 1로, 1은 0으로 바뀐다. "아니다"라는 부정의 의미를 가진다.
• XOR (배타적 논리합, ^): 두 입력이 서로 다를 때만 결과가 1이 된다. A와 B 중 딱 하나만 참일 경우에 참이다.

이러한 불 연산들은 정수 데이터의 각 비트(bit) 단위에 대해 독립적으로 수행될 수 있다. 이것이 바로 비트 연산(Bitwise Operation)이다. 예를 들어, 두 정수의 비트 AND 연산은 각 비트 위치에서 대응되는 두 비트에 대해 AND 연산을 수행하여 새로운 정수를 만들어낸다.

C

unsigned char a = 0b01101001; // 105
unsigned char b = 0b01010101; // 85

unsigned char and_result = a & b; // 0b01000001 (65)
unsigned char or_result = a | b;  // 0b01111101 (125)
unsigned char xor_result = a ^ b; // 0b00111100 (60)
unsigned char not_a = ~a;         // 0b10010110 (150, 8비트 부호 없는 경우)

비트 연산의 활용:

비트 연산은 단순한 논리 연산을 넘어, 다양한 프로그래밍 작업에서 효율성을 극대화하는 데 활용된다.

• 집합 표현 및 조작: 각 비트를 집합의 원소 존재 여부로 매핑하여 효율적인 집합 연산(합집합, 교집합, 차집합 등)을 구현할 수 있다.
• 플래그 관리: 여러 개의 독립적인 boolean 값을 하나의 정수 변수의 각 비트에 할당하여 공간 효율성을 높이고, 비트 마스크(Bit Mask)를 이용해 특정 플래그를 설정, 해제, 검사할 수 있다.
• 하드웨어 제어: Low-level 프로그래밍에서 특정 하드웨어 레지스터의 비트를 조작하여 장치의 동작을 제어하는 데 필수적으로 사용된다. 
• 데이터 압축: 특정 조건 하에서 비트 수준의 조작을 통해 데이터의 크기를 줄이는 데 활용될 수 있다.

2. 데이터의 이동: 논리 시프트와 산술 시프트

시프트 연산(Shift Operation)은 정수의 비트들을 왼쪽 또는 오른쪽으로 이동시키는 연산이다. 이때, 새롭게 생기는 빈 비트 자리를 어떻게 채우느냐에 따라 논리 시프트(Logical Shift)와 산술 시프트(Arithmetic Shift)로 나뉜다.

• 논리 시프트: 왼쪽 시프트(<<) 시에는 오른쪽에 0이 채워지고, 오른쪽 시프트(>>) 시에는 왼쪽에 0이 채워진다. 부호 비트(Sign Bit)를 고려하지 않고 단순히 비트들을 이동시키는 개념이다.
• 산술 시프트: 왼쪽 시프트는 논리 시프트와 동일하게 오른쪽에 0이 채워진다. 하지만 오른쪽 시프트 시에는 최상위 비트(부호 비트)와 동일한 값이 왼쪽에 채워진다. 이는 부호 있는 정수(Signed Integer)의 경우, 오른쪽 시프트 연산 후에도 원래 값의 부호를 유지하기 위함이다.

Shift Operation

부호 있는 데이터 처리 시 유의점:

부호 있는 데이터를 오른쪽으로 시프트할 때는 산술 시프트를 사용하는 것이 일반적이다. 논리 시프트를 사용하면 부호 비트가 0으로 바뀌면서 원래 음수였던 값이 양수로 해석될 수 있기 때문이다. C 언어에서 부호 있는 정수의 오른쪽 시프트 (>>)는 대부분의 컴파일러에서 산술 시프트로 구현되지만, 명확성을 위해 언어 표준을 확인하는 것이 좋다. 부호 없는 정수(Unsigned Integer)의 시프트는 항상 논리 시프트로 취급된다.

3. 메모리 위의 숫자: 부호 있는 정수와 부호 없는 정수

컴퓨터는 정수를 메모리에 저장할 때, 부호 있는(signed) 방식과 부호 없는(unsigned) 방식 중 하나를 선택하여 표현한다.

• 부호 없는 정수(Unsigned Integer): 0과 양수만을 표현하며, 할당된 모든 비트를 값의 크기를 나타내는 데 사용한다. 예를 들어, 8비트 부호 없는 정수는 0부터 255 (\(2^{8}-1\))까지의 값을 표현할 수 있다.
• 부호 있는 정수(Signed Integer): 양수, 음수, 그리고 0을 표현하며, 일반적으로 2의 보수(Two's Complement) 표현 방식을 사용한다. 2의 보수 방식에서는 최상위 비트(Most Significant Bit, MSB)를 부호 비트(Sign Bit)로 사용한다. 0이면 양수, 1이면 음수를 나타낸다. 나머지 비트들은 값의 크기를 나타낸다. 예를 들어, 8비트 부호 있는 정수는 -128 (\(-2^{7}\))부터 127 (\(2^{7}-1\))까지의 값을 표현할 수 있다.

unsigned vs signed

메모리 해석의 차이:

핵심적인 점은 동일한 비트 패턴(Bit Pattern)이라도 어떻게 해석하느냐에 따라 전혀 다른 값이 될 수 있다는 것이다. 예를 들어, 8비트의 비트 패턴 11111111을 생각해 보자.

• 부호 없는 정수로 해석하면 $\backslash (2^\{8\}-1\; =\; 255\backslash )$ 라는 양수 값을 가진다.
• 부호 있는 정수 (2의 보수)로 해석하면 -1 이라는 음수 값을 가진다. (1을 2의 보수로 표현하면 00000001이고, -1은 이 값의 비트를 반전시킨 후 1을 더한 11111111이 된다.)

이처럼 최상위 비트의 해석 방식이 다르기 때문에, 부호 있는 정수와 부호 없는 정수 간의 형 변환(Type Conversion) 시 값의 범위가 달라지거나 예기치 않은 결과가 발생할 수 있으므로 주의해야 한다.

Mapping between Signed & Unsigned

4. 형 변환과 비교 연산의 함정

C 언어와 같이 정적 타입 언어에서 부호 있는 정수와 부호 없는 정수 간의 형 변환(Type Conversion)은 묵시적으로 또는 명시적으로 발생할 수 있다. 이때, 원래 값의 범위가 대상 타입의 범위와 다를 경우 데이터 손실이나 예상치 못한 값 변화가 일어날 수 있다.

또한, 부호 있는 정수와 부호 없는 정수를 비교 연산할 때도 주의해야 한다. C 언어에서는 일반적으로 부호 있는 피연산자가 부호 없는 타입으로 승격(promotion)되어 비교가 수행된다. 이 과정에서 음수가 매우 큰 양수로 해석될 수 있어 논리적 오류를 야기할 수 있다.

소스 코드에 제시된 copy_from_kernel 함수의 예시는 이러한 부호 있는/없는 정수 비교의 위험성을 잘 보여준다. maxlen이 음수로 전달될 경우, len 계산 시 부호 없는 타입으로의 변환으로 인해 매우 큰 양수 값이 되어 버퍼 오버플로우(Buffer Overflow)와 같은 보안 취약점을 발생시킬 수 있다.

Malicious usage

결론

오늘은 불 대수, 비트 연산, 시프트 연산, 그리고 부호 있는/없는 정수 표현 방식에 대해 알아보았다. 이러한 low-level 개념들은 단순히 이론적인 지식을 넘어, 효율적이고 안전하며 예측 가능한 소프트웨어를 설계하는 데 필수적인 기초 체력을 길러준다.

시스템 프로그래밍은 물론, 모든 수준의 프로그래밍에서 데이터의 내부 표현 방식을 정확히 이해하는 것은 문제 해결 능력을 향상시키고 잠재적인 버그를 사전에 방지하는 데 결정적인 역할을 한다. 앞으로도 fundamental한 컴퓨터 과학 지식들을 꾸준히 연마하여, 더욱 깊이 있는 시스템 이해와 혁신적인 소프트웨어 개발 역량을 갖춘 개발자로 성장해 나가길.

다음 시간에는 machine-level로 들어가 더 깊이있게 알아보고자 한다.

추천글:

[시스템프로그래밍] System Program - Compilation System, Runtime System, Operation System

[시스템프로그래밍] Data Representation - number, data storing, data types, byte ordering