[코딩 인터뷰]개념과 알고리즘 - 비트 조작 문제(Python)

 

[ 삽입 ]

 2개의 32비트 수 N과 M이 주어지고, 비트 위치 i와 j가 주어졌을 때 M을 N에 삽입하는 알고리즘

⭐ M은 N의 j번째 비트에서 시작하여 i번째 비트에서 끝납니다. 그리고 j번째 비트에서 i번째 비트까지는 충분한 공간이 있다고 가정합니다.

예시) 입력 : N=10000000000, M=10011, i=2, j=6

         출력 : N=10001001100

def updateBits(n, m, i, j):
    allOnes = ~0
    left = allOnes << (j + 1)
    right = (1 << i) - 1
    mask = left | right
    n_cleared = n & mask
    m_shifted = m << i
    return bin(n_cleared | m_shifted)

👀 정석대로 문제를 풀면 위와 같이 코드를 만들 수 있습니다. 하지만 아래의 방법으로도 문제를 풀 수는 있습니다.

def updateBits(n, m, i, j):
    n = list(str(n))
    m = list(str(m))
    for k in range(j-i+1):
        n[len(n)-(j+i)+k+1] = m[k]
    return int(''.join(n))

 

 

[ 2진수를 문자열로 ]

 0.72와 같이 0과 1 사이의 실수가 주어졌을 때, 그 값을 2진수 형태로 출력하는 알고리즘
⭐ 길이가 32 이하인 문자열 2진수로 표현할 수 없다면 ERROR를 출력하라

# 정수 : whole number    소수 : decimal
def printBinary(n):
    w = int(n)
    d = n - w
    res = "."
    while d > 0:
        if len(res) > 32:
            return "ERROR"
        d *= 2
        res += '1' if d >= 1 else '0'
        d -= 1 if d >= 1 else 0
    return (bin(w).lstrip("0b") if w else '0') + res

👀 소수점 아래의 부분을 2진수로 만드는 법은 소수점 아래의 값에 2를 곱한 다음 그 값이 1보다 크거나 같은지 확인하여 크거나 같으면 1을 입력하고 작으면 0을 입력합니다. 그 후 그 값(2를 곱한 값)이 1보다 크거나 같을 경우 1을 빼줍니다. 문제에서는 0과 1 사이의 실수라고 했지만 모든 실수가 가능하도록 코드를 만들었습니다. while문 안의 if 문 내역만 제거하시면 문자열이 32를 초과하여도 출력합니다.

 

 

[ 비트 뒤집기 ]

 어떤 정수가 주어졌을 때 이 정수의 비트 1개를 0에서 1로 바꿀 수 있을 때 1이 연속으로 나올 수 있는 가장 긴 길이를 구하는 알고리즘

예시) 입력 : 1775    출력 : 8

def flipBit(a):
    tmp = bin(a).lstrip('0b')
    if set(tmp) == {'1'}: return len(tmp)
    nowLength, preLength = 0, 0
    maxLength = 1
    while a != 0:
        if a&1 == 1:
            nowLength += 1
        elif a&1 == 0:
            preLength = 0 if a&2 == 0 else nowLength
            nowLength = 0
        maxLength = max(preLength+nowLength+1, maxLength)
        a = rshift(a, 1)
    return maxLength

def rshift(val, n):
    return (val % 0x100000000) >> n

👀 위의 코드는 정석적으로 정수의 비트값을 읽어 나가면서 현재 1 수열의 길이와 바로 이전 1 수열의 길이만 저장하여 비교하면서 최고값을 찾았습니다. 문자열로 변경하여 위의 풀이와 비슷하게 풀 수도 있지만 아래의 코드는 groupby를 이용하여 '0'이 1개 있을 때 앞 뒤의 1을 개수를 더하여 최고값을 찾았습니다.

from itertools import groupby
def flipBit(n):
    # 2진수와 10진수 구별
    if any([str(i) in str(n) for i in range(2, 10)]):
        n = bin(n).lstrip('0b')
    else:
        n = str(n)
    # groupby를 사용하여 연속되는 1과 0 구분
    group = [(_, len(list(g))) for _, g in groupby(n)]
    result = 0 if not len(group) == 1 else group[0][1]
    for i in range(len(group)):
        if group[i][0] == '0' and group[i][1] == 1:
            tmp = 1
            if i-1 > -1:
                tmp += group[i-1][1]
            if i+1 < len(group):
                tmp += group[i+1][1]
            result = max(result, tmp)
    return result

 

 

[ 다음 숫자 ]

 양의 정수가 하나 주어졌을 때 1비트의 개수가 같은 숫자 중에서 가장 작은 수와 큰 수를 구하는 알고리즘

def getNext(n):
    n = bin(n).lstrip('0b')
    one_cnt = n.count('1')
    zero_cnt = n.count('0')
    return [f"{'0'*zero_cnt}{'1'*one_cnt}", f"{'1'*one_cnt}{'0'*zero_cnt}"]

👀 단순하게 1과 0의 수를 센 뒤 작은 수는 숫자 0을 앞으로 가고 큰 수는 숫자 0을 뒤로 가게 만들었습니다.

 

 

[ 디버거 ]

 다음 코드가 하는 일을 설명하라

( ( n & (n - 1)) == 0)

👀 n과 n-1에 공통적으로 1인 비트(AND연산)가 없다(==0)는 뜻입니다. 즉 n이 2의 거듭제곱수인지 혹은 n이 0인지 검사하는 것입니다.

 

 

[ 변환 ]

 정수 A와 B를 2진수로 표현했을 때, A를 B로 바꾸기 위해 뒤집어야 하는 비트의 개수를 구하는 알고리즘

def bitSwapRequired(a, b):
    cnt = 0
    # 2진수로 변경
    a = bin(a).lstrip('0b') if set(str(a)) != {'0', '1'} else str(a)
    b = bin(b).lstrip('0b') if set(str(b)) != {'0', '1'} else str(b)

    # 자릿수 맞추기
    a = a.zfill(len(b))
    b = b.zfill(len(a))
    
    # 비교
    for i, j in zip(a, b):
        cnt += (i!=j)
    return cnt

👀 수를 2진수로 변환 후 자릿수 맞추고 비교하였습니다.

 

 

[ 쌍끼리 맞바꾸기 ]

 명령어를 가능한 한 적게 사용해서 주어진 정수의 짝수 번째 비트의 값과 홀수 번째 비트의 값을 바꾸는 알고리즘

def swapOddEvenBits(x):
    return (rshift(x&0xaaaaaaaa, 1) | ((x&0x55555555) << 1))

def rshift(val, n):
    return (val % 0x100000000) >> n

👀 Python에서는 논리 시프트(logical shift) >>>를 사용할 수 없기 때문에 직접 함수를 만들어서 사용하였습니다.