# 3개의 명령어로 윤년 여부를 확인하기 > Clean Markdown view of GeekNews topic #20945. Use the original source for factual precision when an external source URL is present. ## Metadata - GeekNews HTML: [https://news.hada.io/topic?id=20945](https://news.hada.io/topic?id=20945) - GeekNews Markdown: [https://news.hada.io/topic/20945.md](https://news.hada.io/topic/20945.md) - Type: GN+ - Author: [neo](https://news.hada.io/@neo) - Published: 2025-05-16T18:33:59+09:00 - Updated: 2025-05-16T18:33:59+09:00 - Original source: [hueffner.de](https://hueffner.de/falk/blog/a-leap-year-check-in-three-instructions.html) - Points: 13 - Comments: 2 ## Summary 3개의 **CPU 명령어**만으로 윤년을 판별하는 함수는 **비트 연산**과 **곱셈**을 사용하여 분기 없는 동작을 구현합니다. 조합적 탐색과 **Z3 SMT Solver**를 활용해 찾은 **매직 상수**로 0~102499년 범위에서 정확하게 동작합니다. 벤치마크 결과에서 분기 없는 방식이 **3.8배 빠른 성능**을 보였으며, 대량의 **무작위 데이터**를 처리할 때 효과적입니다. 함수 내부는 비트 영역별로 **나눗셈 조건**을 결합하여 논리적으로 윤년을 판별합니다. ## Topic Body - **3개의 CPU 명령어**만으로 윤년을 판별하는 함수를 구현함 - 이 방법은 비트 연산과 곱셈을 이용하여 전통적 분기 없이 동작 - 이 방식은 **0~102499년 범위에서 정확함** - 벤치마크 결과 기존 방법 대비 **3.8배 가량 빠른 성능** --- ### 개요 및 문제 제시 - 0에서 102499년 사이의 년도에 대해, 단 **3개의 CPU 명령어만 사용하여 윤년을 판별하는 함수** - 사용되는 실제 함수는 `((y * 1073750999) & 3221352463) <= 126976` 구조임 - 이 비트 트위들링(bit-twiddling) 기법의 원리와 동작, 실질적인 효용성에 대해 설명 ### 전통적인 윤년 판별 방법 - 보통 윤년 판별은 **나눗셈(modulo)와 조건분기로 구현**함 - 4로 나누어 떨어지는지, 100으로 안 나누어지는지, 400으로 나누어 떨어지는지 검사함 - 예시 코드: ``` if ((y % 4) != 0) return false if ((y % 100) != 0) return true if ((y % 400) == 0) return true return false ``` ### 표준 접근 방식의 최적화 - `(y % 100)` 검사를 `(y % 25)`로, `(y % 400)` 검사를 `(y % 16)`으로 대체 가능함 - 그 이유는 앞서 4로 이미 나누었으므로, 25 및 16 곱셈 관계로 변경 가능 - `(y % 25)` 연산을 나눗셈 없이 **곱셈과 비교로 변환**하는 마법 상수 - 예: `x * 3264175145 > 171798691`로 변환 가능 - 비트마스크를 더해 `(y & 3)`이나 `(y & 15)`로 4 또는 16의 나눗셈 대체 가능 - 컴파일러는 이러한 변환을 자동화하지만, 직접 다른 언어에서 활용할 수도 있음 ### 분기 없는(branchless) 구현법 - 분기가 없는 형태로도 변환 가능함: ``` return !(y & ((y % 25) ? 3 : 15)) ``` - 이러한 방식은 코드 골프(coding golf)와 같이 코드 길이 줄이기에 적합 ### 매직 상수 찾기: 비트 트위들링 접근법 - 윤년 판별식을 더욱 **간단하게 만들기 위해 조합적 탐색과 SMT Solver**인 **Z3**를 활용 - 형태: `((y * f) & m) <= t` - 요구 조건을 만족시키는 **상수 f, m, t를 Z3로 탐색** - 0~102499 범위에서 정확한 결과를 얻을 수 있는 값 발굴 - 최종 결과가 `(y * 1073750999) & 3221352463 <= 126976`임 ### 함수 원리 및 내부 구조 해설 - 상수를 이진수로 분석하여, 세 개의 주요 비트 영역 **A, B, C**로 구분함 - 각 영역의 비트 상태에 따라 윤년 판별의 3가지 조건을 포괄함 - 함수의 논리적 분해: - A 영역: `(y % 4) != 0` 여부를 비롯한 4의 배수 조건 확인 - B 영역: `(y % 100) != 0`여부를 다양한 패턴(예: 뒷자리 14, 57, 71 등)로 필터링 - C 영역: `(y % 16) == 0`의 즉, 16의 배수 확인 - 곱셈이 실제로 **나머지 계산 없이 다양한 조건을 결합**해내는 원리 해설 - 매직 상수를 곱할 때, 100의 배수 등에서 특이적인 비트 패턴이 형성됨 - 추가적으로, 곱셈 오차와 여러 자리 숫자 패턴이 등장하는 수학적 내부 구조 분석이 포함됨 ### 추가 범위 및 비트폭 확장 가능성 - 64비트로 확장할 경우 적합한 매직 상수 조합 탐색법도 제시 - `f`, `m`, `t`값을 다양하게 바꿔보며 최장 범위를 찾을 수 있음 - StackExchange에서도 최적 조합 및 Z3 활용 증명 사례가 있음 ### 벤치마크 및 실제 성능 비교 - 벤치마크 결과: - 2025년 등 예측 가능한 값에서는 0.65~0.69ns로 차이가 거의 없음 - 무작위 입력시 `is_leap_year_fast`가 **3.8배 정도 빠른 성능**을 보임 - 입력 패턴에 따라 분기(branching) 방식이 예측 불가할 때 상당한 이점이 있음 ### 결론 및 실제 적용 여부 - 실제 응용에서 값이 예측가능할 때는 이득 적음, 하지만 **대량의 무작위 데이터 상황에선 매우 유용** - 실제 파이썬이나 C# 등 표준 라이브러리 교체 시에는 **현실적인 전체 프로그램 벤치마크**가 필요함 - 아이디어와 구현 방법 자체가 흥미롭고, 특정 상황에서는 성능상 매력적인 솔루션임 ## Comments ### Comment 38874 - Author: chickendreamtree - Created: 2025-05-19T11:09:51+09:00 - Points: 2 Fast inverse sqrt 가 생각나는 글 ### Comment 38758 - Author: neo - Created: 2025-05-16T18:34:00+09:00 - Points: 2 ###### [Hacker News 의견](https://news.ycombinator.com/item?id=43999748) * 최신 컴파일러인 gcc나 clang 같은 경우 is_leap_year1 같은 코드를 is_leap_year2처럼 자동으로 최적화해준다는 사실에 놀라움 느낌, 그래서 C 소스 단계에서 직접 최적화할 필요는 크게 없다는 생각, 하지만 다른 언어에는 여전히 유용함이 있을 수 있음, 특히 cal 프로그램의 최신 버전 소스코드에서 leap year 체크를 아주 간단하게 처리하는 점이 인상적임 * linux 코드가 세 가지 연속된 조건을 매번 반전시키고 기본값 반환을 쓰지 않아 이해하기 훨씬 쉽다는 점이 마음에 듦, 이런 복잡한 코드 구조가 있으면 디버깅할 때 정말 미치는 경험임 * ((y * 1073750999) & 3221352463) <= 126976 이 코드가 어떻게 동작하는지에 대한 설명이 복잡할 수밖에 없다는 데에 전혀 놀라움 없음, 오히려 그게 당연함 * 이해하기 어려운 매직 넘버 최적화 기법을 정말 좋아함, 이런 걸 볼 때마다 예전 어셈블리로 내부 루프 짜던 시절에 얼마나 많은 최적화 기법을 놓쳤을지 궁금함, 혹시 이런 테크닉 모아둔 컬렉션이 있다면 공유 요청 * 여러 비트 조작 트릭 모음 링크 공유, UNIX 스타일 비교에 효율적인 CMP(X, Y) 매크로, signum 함수 최적화 예시, Motorola 68000용 어셈블리 코드 예시 링크, OpenSolaris에서 유래된 비트 매크로 모음 등 다양한 최적화 기법 링크 제공, Open Solaris 블로그는 사라졌다는 아쉬움도 언급, 코드 최적화에 관심 있는 사람들에게 추천 * "Hacker's Delight" 책 추천, 다양한 비트 트릭과 저수준 최적화 기법이 가득함 * supercompilation 기법 찾아보라는 제안 * 예전에는 이런 기법을 놓친 게 아니고, 당시엔 곱셈이 워낙 비쌌기 때문에 저런 게 곧 최적화였음 * 윤년 체크가 이렇게 흥미로울 줄 전혀 예상 못함, 아마 저수준 프로그래머들은 이미 오래전에 이런 트릭을 찾았지만 기록을 남기지 않았던 게 아닐까 하는 생각, 이런 게 아직도 옛 코드 속에 숨어 있을지도 모른다는 느낌, 이런 기법 컬렉션 있으면 정말 탐구해보고 싶다는 열의 * 80년대 z80에서 집에서 직접 배운 것들이 있었는데 대부분 잊어버림, 가끔씩 20대 자녀들에게 보여주면 마치 마술을 부리는 듯한 느낌 * 6000년 이전의 윤년을 알아야 한다면 직접 만든 인터랙티브 계산기와 가시화 도구 사용, 비록 기계 명령어 수는 좀 많지만 아주 빠르게 수천 번의 계산 처리 가능, 수학적 트릭 역시 감탄 포인트 * 비트 조작 챕터를 읽다 "혹시 솔버 쓸 수 있지 않을까" 라는 생각이 들었고, 실제로 글쓴이가 딱 그 방법을 사용해서 깜짝 놀람, 세밀한 접근 방식에 만족 * 이런 윤년 체크 함수를 [current-time-api](https://github.com/alexmacarthur/current-time-api)에 추가하는 게 좋겠다는 제안 * 숫자를 이진수로 보면 재미있는 패턴들이 보임, 모든 소수는 2를 제외하면 1로 끝난다는 점이 흥미로웠음 * 재밌게 보일 수 있지만, 모든 홀수가 1로 끝나고 소수가 본질적으로 2를 제외하면 짝수가 될 수 없으니, 별다른 의미를 못 느끼겠다는 의문 제기 * 윤년 문제에서 0이 없다는 지적이 등장, 사실 "0년"은 없고 1 BC에서 바로 1 AD로 넘어가서 0 체크는 의미 없다는 이야기 * 글 맨 처음을 보면 윤년 알고리즘 설계의 전제가 proleptic 그레고리력과 천문학적 연도를 쓴다는 점이라 설명, 이 조건이 없다면 윤년 체크는 로케일마다 복잡해진다는 점을 강조 * 천문학적 연도 표기를 쓰면 0년이 등장하게 되고, 연/월 관리 등에서는 그렇게 처리하는 것이 오히려 깔끔함, 내부 데이터는 천문학적 표기, 외부 출력만 BCE/CE 변환 제안 * 그레고리력 도입 이전의 달력은 기준 자체가 모호하고 지역마다 다름, 1582년에는 하루에 열흘을 건너뛴 '10일 삭제'도 있었으니, 그 이전 날짜의 연산은 신뢰 불가, 로마 시대 사제들은 윤년을 미신/뇌물 등으로 임의조정하기도 해서 더욱 복잡함 * ISO8601 표준에서는 0년을 허용하고, 천문학적 달력에서 0년은 1 BC의 의미, BCE 연도는 전부 -1만큼씩 오프셋 됨 * 소스코드가 실제로 웃음을 터뜨리게 만드는 경우는 드물기 때문에 아주 즐거운 경험임