---
title: "leading-zero counter: 첫 1을 찾았는데 0 입력에서 틀리는 이유"
author: "브레이브브라우저쓰자"
published_at: "2026-10-11T11:28:03.415Z"
updated_at: "2026-10-06T00:04:03.621Z"
tags: ["leading-zero counter"]
canonical_url: "https://ariser.io/@writer_a9817d5a8de0/leading-zero-counter-%EC%B2%AB-1%EC%9D%84-%EC%B0%BE%EC%95%98%EB%8A%94%EB%8D%B0-0-%EC%9E%85%EB%A0%A5%EC%97%90%EC%84%9C-%ED%8B%80%EB%A6%AC%EB%8A%94-%EC%9D%B4%EC%9C%A0"
ai_assisted: true
---

# leading-zero counter: 첫 1을 찾았는데 0 입력에서 틀리는 이유

이 글은 AI가 활용됐습니다.

[원문](https://ariser.io/@writer_a9817d5a8de0/leading-zero-counter-%EC%B2%AB-1%EC%9D%84-%EC%B0%BE%EC%95%98%EB%8A%94%EB%8D%B0-0-%EC%9E%85%EB%A0%A5%EC%97%90%EC%84%9C-%ED%8B%80%EB%A6%AC%EB%8A%94-%EC%9D%B4%EC%9C%A0)

00000001을 가장 높은 자리부터 검사하면 일곱 번 0을 만난 뒤에야 1을 찾는다. 64비트나 128비트 입력에서도 이런 순서대로 검사해야 할까. leading-zero counter는 앞에서 연속된 0의 개수를 구하지만, 회로는 **여러 구간에 1이 있는지 병렬로 판단하며 검색 범위를 좁힐 수 있다.**

이 값은 숫자를 정규화할 때 유용하다. 첫 1의 위치를 알면 유효한 숫자 부분을 어느 만큼 이동해야 하는지 정할 수 있다. 여기서는 그 위치를 찾는 회로와 0 입력의 의미에 집중하자.

## 8비트를 반으로 나누어 찾아보기

입력 00100010의 leading zero 수는 2다. 높은 네 비트 0010에 1이 있으므로 답은 그 구간에 있다. 그 안의 높은 두 비트 00에는 1이 없고, 낮은 두 비트 10에는 있다. 따라서 앞의 두 비트를 건너뛰고 10의 첫 자리가 1임을 확인한다.

각 구간은 두 정보를 만들 수 있다. 구간에 1이 있는지 나타내는 valid와, 있다면 그 구간 안의 첫 1 위치다. 높은 구간이 valid이면 그 결과를 선택한다. 높은 구간이 비어 있고 낮은 구간이 valid이면 높은 구간의 길이를 더한 낮은 결과를 선택한다.

이 관계를 두 비트, 네 비트, 여덟 비트 구간으로 반복하면 tree를 구성할 수 있다. 각 구간의 존재 여부는 OR 계열 논리로, 선택 위치는 mux와 위치 정보로 전달된다. 모든 비트를 직렬로 한 번씩 검사하는 개념과 달리 여러 하위 구간의 계산이 동시에 진행된다.

[PULP의 leading/trailing zero counter](https://github.com/pulp-platform/common_cells/blob/master/src/cc_lzc.sv)는 선택 노드와 위치 노드를 나누어 트리로 연결하는 공개 구현이다. leading 모드에서는 비트 순서를 변환해 같은 우선순위 검색 관계를 재사용한다. 기능의 “앞”이 회로에서 어떤 방향인지 확인해야 한다.

## 숫자 0의 답에는 한 비트가 더 필요하다

32비트 입력에서 첫 1의 위치는 0–31이다. 다섯 비트로 표현할 수 있다. 하지만 모든 입력이 0이면 leading zero 수는 32다. 그 값까지 같은 출력에 담으려면 여섯 비트가 필요하다.

따라서 어떤 인터페이스는 별도의 empty 또는 all-zero 신호를 사용한다. 위치 값은 0–31 범위를 담고, all-zero일 때 그 위치를 정상 숫자로 해석하지 않는 계약이다. 다른 인터페이스는 출력 자체에 32를 담는다. 둘은 기능적으로 대응시킬 수 있지만 포트의 숫자 의미가 다르다.

확인한 PULP 구현은 empty_o로 0 입력을 알린다. 입력 폭이 2의 거듭제곱인 구성에서는 all-zero의 cnt_o가 최대 위치 값에 해당하는 결과를 낸다. 8비트 입력이 모두 0이면 empty_o=1이고 cnt_o를 “0이 7개뿐이다”라는 독립 결과로 소비해서는 안 된다. source의 계약은 두 출력의 조합으로 읽어야 한다.

| 8비트 입력 | 앞의 0 개수 | 결과 해석 |
|---|---:|---|
| 10000000 | 0 | 첫 자리가 1 |
| 00100010 | 2 | 세 번째 자리가 첫 1 |
| 00000001 | 7 | 마지막 자리가 첫 1 |
| 00000000 | 8 | 1이 없음, 별도 규칙 필요 |

표의 개수는 수학적인 정의다. 특정 모듈의 count 포트가 마지막 행의 8을 직접 낸다고 주장하는 표가 아니다.

## 0을 이동시켜도 정규화된 1은 나오지 않는다

정규화 회로가 all-zero를 무시하고 count 값만 shifter에 보내면, 없는 첫 1을 정상 위치처럼 취급할 수 있다. 입력 0은 얼마나 이동해도 0이므로 숫자 비트만 보면 오류가 숨을 수 있다. 하지만 지수 보정이나 valid 상태는 잘못 갱신될 수 있다.

예를 들어 정상 입력 00000001과 0 입력을 같은 위치 값 7로 처리하면, 두 경우 모두 지수를 같은 만큼 바꾸는 제어가 실행될 수 있다. 하나는 유효 숫자를 이동하는 동작이고, 다른 하나는 별도의 zero 결과여야 한다. 위치 계산이 맞아도 all-zero 처리의 관측 계약이 틀리면 전체 숫자 의미가 달라진다.

그 밖의 입력에서도 count는 가장 높은 1의 위치만 알려 준다. 이동 중 잘라내는 낮은 비트와 반올림에 필요한 정보까지 제공하지는 않는다. 위치 탐지와 이후 숫자 변환의 책임을 분리해야 한다.

## 입력 폭이 2의 거듭제곱이 아니면

7비트나 24비트 입력을 균형 트리에 넣으려면 마지막 구간의 길이와 존재하지 않는 자리를 처리해야 한다. 단순히 높은 쪽에 0을 추가한 뒤 더 넓은 leading-zero 개수를 그대로 반환하면 원래 입력에 없는 0까지 셀 수 있다.

없는 자리는 후보가 없다는 정보로 취급하고, 실제 위치와 구간 길이를 유지하거나 최종 count의 기준을 보정해야 한다. source의 PULP 코드도 범위 밖 노드를 별도 처리한다. parameter가 여러 폭을 허용한다고 해서 우연히 사용하는 32비트만 시험하면 범위 경계 오류를 놓칠 수 있다.

Width=1은 또 다른 경계다. 일반적인 `$clog2(1)`은 0이므로 포트 폭을 그대로 만들면 선언 문제가 생길 수 있다. 작은 폭을 별도 처리하거나 최소 index 폭을 정하는 구현 정책이 필요하다. 원문의 단일 비트 분기는 이런 경계를 드러낸다.

## 트리의 이득을 어디까지 기대할까

균형 검색은 구간 크기를 두 배씩 늘려 위치를 찾는다. 하지만 노드의 선택 경로와 배선, 위치 비트의 부하가 실제 지연을 정한다. 전체 위치를 만들 필요 없이 “높은 절반이 비었는가”만 필요한 회로는 더 단순할 수 있다. 반대로 넓은 normalization 경로에서는 이후 shifter가 더 긴 임계 경로일 수 있다.

검증은 첫 1을 모든 위치로 옮긴 one-hot 입력과 0 입력부터 시작하면 명확하다. 여러 1이 있으면 높은 위치가 우선하는지도 확인한다. 결과 폭, empty 처리와 parameter 경계를 같은 검사에 포함해야 숫자와 인터페이스가 일치한다.

leading-zero counter가 빨라질 수 있는 이유는 0을 하나씩 세지 않고 구간의 존재 정보를 병렬로 합치기 때문이다. **좋은 구현은 첫 1을 빠르게 찾는 것에 더해, 1이 없는 입력과 실제 폭 밖의 자리를 정확히 구분한다.** 첫 1의 위치보다 먼저 count가 언제 유효한 숫자인지 정하는 것이 설계의 출발점이다.