이진 카운터 편집하기

이진 카운터(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)의 직관적 예시
==파이썬 예제==
<syntaxhighlight lang="python">
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()
</syntaxhighlight>
==같이 보기==
*[[이진수]]
*[[플립플롭]]
*[[비트 연산]]
*[[디지털 회로]]
*[[분할 상환 분석]]
==참고 문헌==
*Donald E. Knuth, ''The Art of Computer Programming'', Vol. 1: Fundamental Algorithms, Addison-Wesley.
*Thomas H. Cormen et al., ''Introduction to Algorithms'', MIT Press.
==각주==
[[분류:알고리즘]]