이진 카운터
더 많은 작업
이진 카운터(binary counter)는 이진수 표현을 이용하여 정수 값을 하나씩 증가시키는 계산 장치 또는 알고리즘적 구조이다.
이진 카운터는 0과 1의 이진수 형식으로 정수를 표현하며, 각 증가 연산 시 비트를 오른쪽부터 왼쪽으로 올려가며 반전시키는 방식으로 동작한다. 일반적인 이진 덧셈 규칙을 따르며, 하드웨어 회로 또는 알고리즘의 일부로 자주 사용된다. 대표적으로 하드웨어에서는 플립플롭을 이용한 동기식/비동기식 카운터가 있고, 소프트웨어에서는 반복문에서의 반복 횟수 제어나, 비트마스크 기반의 상태 표현 등에 사용된다.
이진 카운터는 정수 0에서 시작하여 매번 1씩 증가하는 방식으로 작동한다. 각 비트는 이전 비트가 1에서 0으로 바뀌는 시점에서 반전된다.
예를 들어 3비트 이진 카운터의 동작 순서는 다음과 같다:
- 000 → 001 → 010 → 011 → 100 → 101 → 110 → 111
이러한 방식으로 카운터는 2ⁿ - 1까지의 값을 표현할 수 있다(여기서 n은 비트 수).
이진 카운터는 분할 상환 분석의 대표적인 예로 자주 인용된다. 하나의 증가 연산에서 여러 비트가 반전되기 때문에, 최악의 경우 O(log n)의 시간이 걸릴 수 있다. 그러나 일련의 연산 전체를 분석하면 평균적인 비용은 훨씬 낮다.
예를 들어 n번의 증가 연산이 있다고 가정하자. i번째 비트는 2ⁱ번마다 한 번씩 반전된다. 따라서 n번의 증가 동안 i번째 비트가 반전되는 횟수는 ⌊n / 2ⁱ⌋이다. 이를 모든 비트에 대해 합산하면 총 반전 횟수는 다음과 같다:
- 총 반전 수 ≤ n(1/2 + 1/4 + 1/8 + …) < 2n
따라서 평균적으로 각 증가 연산당 비트 반전 횟수는 O(1)에 해당한다. 이는 분할 상환 분석의 aggregate method 또는 accounting method로 설명된다.
이러한 분석은 이진 카운터를 기반으로 한 자료구조(예: 동적 배열의 크기 조절, 최소 힙 삽입 등)의 평균 성능을 이해하는 데 중요한 도구가 된다.
이진 카운터는 다음과 같은 분야에서 널리 활용된다.
- 하드웨어 설계에서의 클럭 기반 카운터
- 소프트웨어 알고리즘에서의 비트 기반 상태 추적
- 아멀티큐 시뮬레이션, 비트 벡터 연산
- 분할 상환 분석(amortized analysis)의 직관적 예시
class BinaryCounter:
def __init__(self, bits):
self.bits = bits
self.value = 0
def increment(self):
self.value += 1
if self.value >= 2 ** self.bits:
self.value = 0
def get_binary(self):
return format(self.value, f'0{self.bits}b')
# 사용 예시
counter = BinaryCounter(3)
for _ in range(10):
print(counter.get_binary())
counter.increment()
- Donald E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addison-Wesley.
- Thomas H. Cormen et al., Introduction to Algorithms, MIT Press.