1. 패러티 비트 계산하기.
문제
패러티 비트는 시리얼 통신에서 데이터 전송 중 발생하는 잡음에 의한 변화를 검출하는데 사용된다. 패러티 비트는 입력 데이터의 2진수 표현에서 1의 개수를 세고, 이 개수가 짝수이면 0, 홀수이면 1로 계산된다. 64비트 정수가 계속해서 입력되는 환경이라고 하자. 이때 입력 데이터들에 대한 패러티 비트를 계산하는 프로그램을 작성하라. (입력되는 데이터는 64비트 정수이며 매우 많은 양이라고 가정한다.)
해결
간단한 방법으로는 입력 데이터의 최하위 비트를 1과 and 연산을 취하고 왼쪽 쉬프트 연산을 하며 개수를 일일이 세는 것이다. 이러한 방법은 n비트 데이터에 대해 O(n)의 성능을 보인다.
a = int(input())
parity = 0
while a > 0 :
parity ^= (a & 1)
a >> 1
return parity매우 많은 데이터가 입력되는 환경에서 매번 일일이 세는 것은 비효율적으로 보인다.
x & (x - 1)
이 연산은 x의 LSB를 0으로 만든다. 이 연산을 x가 0이 될 때까지 반복하면 반복 횟수는 1인 비트의 개수와 같다. 따라서 위의 코드는 아래와 같이 개선된다.
a = int(input())
parity = 0
while a > 0 :
parity ^= 1
a &= (a - 1)
return parity- 참고로 x & ~(x-1) 연산은 최하위의 1인 비트만을 남기고 모두 0으로 만든다.
1의 개수가 짝수인지 홀수인지를 알기 위해 xor 연산을 사용했다. xor의 진리표는
두 개의 피연산자 논리값이 서로 다를 때에만 1을 출력한다. xor을 이용하면 긴 비트열에서 1이 짝수개인지 홀수개인지 추가적인 계산없이 판단할 수 있다.
64비트 정수를 절반으로 분할하며 분할된 양 부분을 xor을 해나가면 6번의 연산으로 1개의 비트를 얻을 수 있다.
64 -> 32 xor 32 -> 하위 32비트 -> 16 xor 16 -> 하위 16비트 -> ... -> 하위 1비트
이 비트는 전체 중 1의 개수가 홀수인지 짝수인지의 정보를 표현한다. 따라서 반복문을 사용하던 기존 방식을 개선하여 O(log n)의 성능으로 개선할 수 있다.
a = int(input())
a ^= a >> 32
a ^= a >> 16
a ^= a >> 8
a ^= a >> 4
a ^= a >> 2
return (a ^ a >> 1) & 1
더 빠른 방법을 알아냈지만 여전히 매우 많은 데이터가 입력되면 매번 이 연산을 수행해야한다.
이 점을 해결하기 위해 미리 패러티 비트 값을 저장해두는 룩업 테이블을 활용한다.
16비트로 이루어진 모든 이진수의 패러티 비트를 계산하는 것은 부담스럽지 않다. 따라서 2의 16제곱 크기의 배열을 선언하여 여기에 미리 모든 패러티를 저장한다. 그다음 64비트 입력을 다음 프로그램에 적용한다.
def getParity(i_data) :
mask = 0xffff
return (preComputedParity[i_data & mask] ^
preComputedParity[(i_data >> 16) & mask] ^
preComputedParity[(i_data >> 32) & mask] ^
preComputedPairty[(i_data >> 48) & mask]2. 비트 스왑
문제
64비트 정수가 주어졌을 때, i번째와 j번째 비트를 서로 바꾸는 프로그램을 작성하라.
해결
두 비트를 바꾸는 방법은 단순히 보자면 어려워 보인다. i, j 비트를 어딘가에 저장하고 해당 위치를 0으로 만든 뒤 i, j 번 시프트하여 or 연산을 수행한다. 이런 방식은 추가적인 메모리를 소모하며 효율적이지 못하다.
i, j비트가 가질수 있는 경우를 생각해보자.
각 비트가 (0, 0), (0, 1), (1, 0), (1, 1)인 경우가 있다.
눈치를 챘겠지만 00, 11인 경우엔 비트를 바꾸는 것은 의미가 없다. 따라서 1,0 혹은 0, 1인 경우만 신경쓰면 되는데 이 마저도 각 비트를 반전 시키는 것만으로 뒤바꾸는 것과 동일한 결과가 된다.
어떤 비트를 반전시키는 방법은 다양하지만 대표적으로는 1과 xor 연산을 수행하는 것이다.
우선 두 비트가 다른지 확인한다. 만약 다르다면 i, j 번 비트만 1인 마스크과 xor 연산을 수행한다.
def swapBits(x, i ,j) :
if (x >> i) & 0x1 != (x >> j) & 0x1:
return x ^ ((0x1 << i) | (0x1 << j))
return x3. 비트 뒤집기
문제
64비트 숫자가 주어졌을 때 이를 역순으로 재구성하라. 정수 데이터가 매우 많이 입력된다고 가정하라.
(예시 : 11100110은 01100111이 된다.)
해결
특정 위치의 비트를 뒤집는 알고리즘은 2번 문제와 동일하다. 64비트 정수를 가장 자리부터 대칭적으로 32번 차례로 스왑하면 뒤집어진다.
매우 많은 데이터가 입력될 때, 매번 연산을 수행하는 것은 부담스럽다. 1번 문제와 같이 미리 결과를 룩업 테이블에 저장해두면 이를 이용해 빠르게 계산할 수 있다.
# 2**16 크기의 룩업 테이블을 생성한다.
tbl = []
for i in range(2 ** 16) :
t = i
for j in range(8) :
t = bit_swap(t, 15 - j, j)
tbl.append(t)
def reverse_bits(n) :
mask = 0xffff
return (tbl[(n >> 48) & mask]) |
(tbl[(n >> 32) & mask] << 16) |
(tbl[(n >> 16) & mask] << 32) |
(tbl[n & mask] << 48)4. 같은 무게를 가진 가장 가까운 정수 찾기
문제
음이 아닌 어떤 정수 x가 주어진다. x의 무게란 x의 이진표현에서 1인 비트의 개수이다. x와 같은 무게를 가지면서 |x - y| 가 최소가 되는 음이 아닌 정수 y를 찾아라. x의 모든 비트가 0이거나 1인 경우는 고려하지 않는다.
해결
어떤 비트열이 주어졌을 때, 이 비트열과 차이가 가장 작아지기 위해선 최하위 비트 주변에서 변화가 일어나는 편이 차이가 적을 것이다. 무식한 방법으로는 1의 개수를 세면서 1씩 증가, 1씩 감소를 동시에 수행하며 값을 찾는 것이다. 이런 방식은 x의 값이 커질수록 매우 많은 연산을 필요로 할 것이다. 2의 32제곱이 x로 주어지면 이는 2의 거듭제곱이므로 무게가 1이다. 무식한 방법을 적용하면 2의 31제곱 까지 2의 32제곱 - 2의 31제곱 번을 반복한다.
어떤수 x와 가장 가까우며 무게가 같은 정수는 어떤 특징을 가지는가.
이 수를 y라고 하면, y < x일때 y는 x보다 작고 무게는 같은 가장 큰 값이 된다. y > x라면 y는 x보다 크며 무게는 같은 가장 작은 값이 된다.
64비트 중 하위 비트만 놓고 봤을 때,
.... 0000 1111 인 경우, 상위 부분의 비트를 건드리지 않고 하위의 연속된 부분만으로 같은 무게를 찾을 수 있으며, 차이도 가장 작아질 것이다.
근데 이 경우 0 1111 보다 값이 작아지면 자연히 무게는 4보다 작아지므로 불가능하다. 즉, 0 1111을 증가시키는 방식으로 y를 찾아야한다.
교체되는 두 비트 위치를 k1, k2 라고 할 때, 2의 k1제곱 - 2의 k2제곱이 최소가 되어야 한다. 그러기 위해선 k1과 k2의 차이가 1이어야 하며, 이는 서로 이웃한 비트임을 의미한다.
0 1111과 무게가 같으며 가장 가까운 정수는 1 0111이다.
1 0000은 어떠한가. 0 1000이 무게가 같으며 가장 가까운 정수가 된다.
이상의 내용을 정리하면 최하위 비트부터 처음으로 다른 값이 나오는 비트 위치를 찾고 이 이전 비트와 이 비트를 반전시킨다.
def closestSameBitCount(x) :
i = 1
while (x >> i) & 1 == (x >> (i-1) & 1 : i += 1
return x ^ ((1<<i) | (1 << (i-1)))이 알고리즘의 성능은 비트의 길이가 n일 때 O(n)의 시간복잡도가 된다.
이 알고리즘을 O(1)의 성능으로 개선하는 것도 가능하다.
비트가 반전되는 위치가 연속된 비트의 마지막임을 눈여겨보자.
최하위 비트가 0인 경우 반전되는 위치는 x의 최우측의 1이다. 논리 연산을 사용하면 손쉽게 최하위 비트만 추출할 수 있고, 이것을 이용해 비트 마스크를 생성하면 반복문 없이 위치를 특정할 수 있다.
최하위 비트가 1인 경우에는 반전을 해주기만 하면 된다.
def closestSameBitCount(x) :
flag = x & 1
x = ~x if flag else x
mask = x & ~(x-1)
mask |= mask >> 1
x ^= mask
x = ~x if flag else x
return x5. 곱셈과 덧셈 없이 x * y 계산하기
문제
저전력 기기에선 곱셈 연산기가 없는 경우가 있다. 로우 레벨의 원시적인 방법으로 음이 아닌 두 정수의 곱셈을 구현하라.
아래 연산자들만 사용 가능하다.
1. 대입 연산자
2. 비트 연산자
3. == 연산자, bool 조합 연산자
산술연산자, 증감 연산자(++나 --), 비교 연산자 사용은 불가능하다.
해결
가장 간단한 방법은 x를 y번 더하는 것이다. 이를 위해 덧셈 함수를 구현해야하며, O(n)의 시간복잡도를 갖게된다.
이것은 비효율적이기 때문에 더 효율적인 곱셈 방법을 찾아야한다.
곱셈을 할 때 일일이 더하는 사람은 없다. 자릿수에 맞춰 곱하고 이 결과들을 합해 최종 결과를 얻는 방식으로 곱하기를 계산한다.
2진수 곱셈에서 k번 비트가 1인 수와 곱셈을 수행하면 x를 k번 오른쪽 시프트하는 것과 같다. 시프트 연산을 사용할 수 있다면 덧셈 함수를 만들어 곱셈을 쉽게 계산할 수 있다.
덧셈 함수는 or과 xor을 사용한다. xor은 자리올림 없는 덧셈을 수행한다. 전가산기(Full adder)는 산술 덧셈을 구현하며, 자리올림이 발생하면 상위 비트에 반영한다.
이런 덧셈은 2가지 단계로 분리된다. 1. 자리올림(이하 carry)없는 덧셈을 수행한다. 2. carry를 계산해 반영한다.
carry의 반영도 결국 덧셈이므로 위 2개의 단계를 carry가 발생하지 않을 때까지 반복한다.
def add(a, b) :
while (b) :
carry = a & b # 이진수 1과 1을 더할 경우에만 캐리가 발생한다.
a ^= b # 논리 합을 수행한다.
b = carry << 1 # 캐리를 더해주기 위한 조치
return a곱셈은 덧셈 함수를 사용한다.
def multiply(a, b) :
res = 0
while (b) :
res <<= 1
if b & 1 : res = add(res, a)
b >>= b
return res