2진법이 어려운 나을 위한 비트 연산자 탐구 [Algorithm #4]

평소처럼 코테 문제를 풀다가 내게 상당히 어려운 이진법 문제를 만났다. 당연히 비트 연산자를 날잡고 공부한 적 없는 나는 손도 못 댔다. 그래서 오늘 좀 정리하고 넘어가보려 한다.

 

1. 비트 연산자 종류

a << b  : a를 b만큼 왼쪽으로 shift하는 연산을 말한다.

일반적으로 1 << n을 많이 사용하는데, 1 << 3 : 1000가 되는 것이다.

 

a & b : AND 연산자이다. 둘 다 1일 경우 1을 반환하고, 하나만 0이어도 0을 반환한다.

 

a | b : OR 연산자이다. 둘 중 하나만 1이어도 1을 반환하고, 둘 다 0일 경우 0을 반환한다.

 

a ^ b : XOR 연산자이다. 둘이 같으면 0을 반환하고, 다르면 1을 반환한다.

이를 이용하여 Toggle을 만들 수 있다.

A ^= True

A가 True라면, True ^ True = 0 = False가 되고

A가 False라면, False ^ True = 1 = True가 되어 무조건 A를 토글하게 된다. 알아두면 쓸 일이 많을 것 같다.

 

~n : 여집합 연산자로, 1을 0으로 / 0을 1로 전환하는 연산을 말한다.

예를 들어 n = 10111이면, ~n = 01000가 된다.

 

-n : 2의 보수 연산자이다.

제대로 이해하려면 보수에 대해 조금 알아야 하는데,먼저 1의 보수는 주어진 수를 111.....같은 (2의 제곱수 - 1)로 만들기 위해 더해야 하는 수이다.이는 111....에서 주어진 수를 빼서 구할 수 있다. 1에서 0을 빼면 그대로 1이고, 1을 빼면 0이 되니 주어진 수의 모든 비트를 뒤집는 것과 같다.

 

2의 보수는 주어진 수를 100...00같은 2의 제곱수로 만들기 위해 더해야 하는 수이다. 이는 1의 보수를 구해서 1을 더한 것과 같으니, 주어진 수의 모든 비트를 뒤집고 1을 더한 것과 같다.모든 비트를 뒤집는 연산은 ~n이니까,

-n = ~n + 1

가 성립한다.

 

2. 유용한 연산 모음

1 << n 은 n번째 비트만을 1로 켜는 연산이다. 1 << 4 = 10000

그런데 최대 비트가 1이고 나머지가 모두 0이면, 1을 빼면 최대 비트가 0이 됨가 동시에 나머지가 1이 된다.

n개의 비트를 1로 켜는 연산   :   (1 << n) - 1

 

 

원하는 자리수의 비트를 1로 전환하고 싶다면, OR 연산자를 이용하여 구현할 수 있다. (이미 1이면 유지)

n번째 비트를 1로 켜는 연산   :   X |= (1 << n) 

 

 

반대로 원하는 자리수의 비트를 0으로 전환하고 싶다면, 여집합 연산자와 AND 연산자를 이용하여 구현할 수 있다. (이미 0이면 유지)

n번째 비트를 0으로 끄는 연산   :   X &= ~(1 << n) 

 

 

주어진 숫자에서 1인 비트 수를 세는 연산은 어떻게 구현할까?

재귀 함수를 이용해, n을 2로 나누면서 나머지가 1인 경우를 모두 더해서 반환하게 구현할 수 있다.

 

def count_bit(n):
    return n % 2 + count_bit(n // 2) if n >= 2 else n

 

하지만 비트 마스킹을 적극 활용하고 싶다면 아래와 같이 구현할 수도 있다.

 

def bit_count(n):
    k = 0
    count = 0

    while n >= (1 << k):
        if n & (1 << k) != 0:
            count += 1
        k += 1

    return count

 

07.30 추가

가장 낮은 비트 1을 찾는 방법은 n & -n == n & ~n+1 이다.

모든 비트를 뒤집고 1을 더하면, 주어진 수의 가장 낮은 1은 0이 되었다가 뒤에서부터 1을 더해져 최종적으로 1이 된다.

원래 0이었다가 뒤집어서 1이 된 비트는 AND 연산자에서 걸러진다.

최하위비트 (1) 찾기   :   X & -X      or     X & ~X + 1 

가장 낮은 비트 0은 어떻게 찾을까?

가장 낮은 비트 1을 찾는 방법에서 주어진 수를 뒤집어 이용하면 될 것이다.

n 대신 ~n을 넣으면, ~n & n + 1이 된다.

최하위비트 (0) 찾기   :  -X & X + 1 

 

 

 

이제 겨우 첫걸음을 뗐으니 열심히 문제를 풀어봐야겠다..

 

Reference

-https://rinrin-dev.tistory.com/55

-https://shoark7.github.io/programming/knowledge/some-useful-bit-tricks-and-usages