[Algorithm] 비트 마스킹

부울 연산자

AND, OR, NOT은 기본 부울 연산자로, 연산들을 서로 결합하거나 조합해 다른 보조 연산을 만들어 낼 수 있다. XOR이 보조 연산에 해당하며, 기본 연산의 조합으로 다음과 같이 XOR을 구성할 수 있다.

x = y = True
(x and not y) or (not x and y)
# False

 

1. XOR

    - 다르면 1, 같으면 0

      0 ^ 0 = 0

        0 ^ 1 = 1

        1 ^ 0 = 1

        1 ^ 1 = 0

 

2. AND

    - 논리곱: 곱하기처럼 생각하면 쉽다.

        0 & 0 = 0

        0 & 1 = 0

        1 & 0 = 0

        1 & 1 = 1

 

3. OR

    - 논리합: 더하기처럼 생각하면 쉽다.

        0 | 0 = 0

        1 | 0 = 1

        0 | 1 = 1

        1 | 1 = 1

 

비트 연산자

비트 연산자는 &, |, ^, ~ 을 사용하며, 비트 연산자도 부울 연산자와 동일하게 잘 작동한다. 하지만, 비트 연산자 NOT인 ~ 는 정수에 적용할 때 모든 비트를 반전한다. 부울 값(True/False)에 적용하면, True는 정수 1로 간주되고 False는 정수 0으로 간주된다.
따라서 ~True는 ~1로 계산되어 결과는 -2가 되고, ~False는 ~0으로 계산되어 결과는 -1이 된다. 비트 연산자 NOT은 2의 보수에서 1을 뺀 값과 같기 때문이다. 따라서 십진수로 표현할 때는 NOT x = - (x+1) 이 된다.

 

자릿수 제한 비트 연산

보통 ~0b1100은 0b0011이 되고, 따라서 0b0101 ^ ~0b1100 = 0b0110을 기대하고 있을 것이다. 그런데 결과는 -0b1010으로 전혀 다른 값이 나온다. 이 이유는 ~ 연산자는 비트 단위로 값을 뒤집는데, 컴퓨터 내부에서는 숫자가 고정된 비트 수 (예: 32비트 또는 64비트)로 표현된다. 따라서, ~0b1100은 단순히 4비트 값만 반전하지 않고, 모든 비트를 반전한다. 즉, 내부적으로는 32비트로 처리 되기 때문에 ~0b0110은 111111...110110이 된다. 따라서 자릿수 제한 비트 연산으로 기대 결과값을 도출해내야 한다.

비트 마스크는 특정 비트의 범위를 제한하거나 필요한 부분만 추출할 때 사용한다. 따라서, 32비트 값 대신 필요한 자릿수(예: 4비트)로 제한하기 위해서는 비트 마스크를 적용하면 된다.

MASK = 0b1111 # 4비트로 제한
bin(0b0101 ^ (0b1100 ^ MASK))
# 0b110

 

2의 보수

2의 보수는 컴퓨터가 음수를 저장하기 위해 일반적으로 취하는 여러 방법 중 하나이다. 4비트를 예로 들면, 표현 가능한 범위는 0000부터 1111까지이다. C언어의 unsigned(부호 없는 정수) 타입으로 선언하면 양수 0~15까지 저장되겠지만, 기본적으로는 음수까지 고려해야 한다. 따라서 맨 앞 비트를 부호 비트(MSB)로 설정하여 -8 ~ 7까지 표현이 가능하다. 양수의 경우 0xxx를 사용하고, 음수는 1xxx를 사용한다. 만약, 2의 보수를 4비트로 제한하고 싶다면 비트 마스크를 사용하면 된다. MASK를 이용해 음수 값도 4비트 내에서 표현 가능하다.

MASK = 0xF # 0b1111
bin(1 & MASK)
# 0b1
bin(7 & MASK)
# 0b111
bin(-8 & MASK)
# 0b1000
bin(-7 & MASK)
# 0b1001
bin(-1 & MASK)
# 0b1111

 

2의 보수 수학 연산은 쉽게 말해 양수를 음수로, 음수를 양수로 바꾸는 작업을 말한다. 2의 보수를 구하는 두 가지 단계는 다음과 같다.

1.  비트를 반전한다. (비트 연산자 NOT을 구한다.)
2. 1을 더한다.

-  숫자 7 (0111):

    비트를 뒤집는다 → 1000

    1을 더한다 → 1001 (결과: -7)

 

-  숫자 -7 (1001):

    비트를 뒤집는다 → 0110

    1을 더한다 → 0111 (결과: 7)

 

따라서 2의 보수는 비트 연산자 NOT + 1이라는 결과를 도출해낼 수 있다. 

 

 

-  0111의 2의 보수를 구해보자.

    0111의 비트를 뒤집으면 → 1000

    여기에 1을 더하면 → 1001 (2의 보수 결과)

 

-  1001의 비트 연산자 NOT을 구해보자.

    1001의 비트를 뒤집으면 → 0110

    (1을 더하지 않음)