C++에서 효율적인 uint128 직접 구현하기: u64 두 개로 끝내기
C++로 128비트 부호 없는 정수(u128)를 다뤄야 하는데, 컴파일러 내장형 __uint128_t를 못 쓰거나(특히 MSVC), 플랫폼별 동작을 더 “예측 가능하게” 만들고 싶을 때가 있습니다. 이 글은 u128을 u64 두 개(상위/하위 limb)로 표현하고, x64 인트린식으로 덧셈·뺄셈·곱셈·비교를 구현해 내장형에 가까운 성능을 얻는 방법을 한 번에 정리합니다.1
핵심은 단순합니다. “고정 폭 정수(Fixed-width)”는 필요한 비트 수가 딱 정해져 있을 때, BigInt처럼 동적 메모리·분기·인디렉션 비용을 피하면서도, CPU가 잘하는 방식(캐리/보로우 플래그 기반)으로 계산을 밀어붙일 수 있다는 점입니다.1
u128 설계: 두 개의 u64 limb로 표현하는 고정 폭 패턴
가장 흔한 표현은 lo(하위 64비트), hi(상위 64비트) 두 필드입니다. 이 구조가 좋은 이유는 확장성이 깔끔하기 때문입니다. u128이 익숙해지면 같은 패턴으로 192비트(3 limb), 256비트(4 limb)도 거의 복붙 수준으로 늘릴 수 있습니다.
또 하나의 장점은 “캐리(carry)와 보로우(borrow)를 눈에 보이게 관리한다”는 점입니다. BigInt는 내부에서 이 일을 해주지만, 고정 폭에서는 우리가 직접 처리하되, 인트린식을 쓰면 결국 CPU 플래그를 그대로 활용하는 코드가 나옵니다.1
덧셈·뺄셈: _addcarry_u64 / _subborrow_u64로 오버헤드 없이
u128 덧셈의 본질은 “하위 64비트 더하고 캐리가 나면 상위에 1 더하기”입니다. 이때 x64에서는 ADC(add with carry)라는 전용 명령이 있고, 컴파일러 인트린식 _addcarry_u64가 여기에 거의 1:1로 대응됩니다.1
구현은 대략 이런 흐름입니다. 먼저 lo를 더하면서 캐리를 얻고, 그 캐리를 hi 덧셈에 포함합니다. 뺄셈도 동일하게 _subborrow_u64로 보로우를 다음 limb로 전달하면 됩니다.1
여기서 중요한 포인트는 “추상화 비용이 끼어들지 않도록” 만드는 겁니다. 인라인 어셈블리는 이식성과 최적화 관점에서 발목을 잡기 쉬운데, 인트린식은 컴파일러가 문맥을 보며 레지스터 할당과 최적화를 하기 좋습니다. 결과적으로 내장형 __uint128_t가 생성하는 코드와 거의 같은 형태로 수렴하는 경우가 많습니다.1
곱셈 최적화: 128×128은 256이지만, 우리는 하위 128만 쓴다
u128끼리 곱하면 수학적으로는 256비트 결과가 나오죠. 하지만 많은 실전 코드(해시, 모듈러 연산의 일부, 고정 폭 누산 등)는 “하위 128비트만 필요”한 경우가 꽤 있습니다. 이때 상위 결과를 끝까지 만들려고 애쓰면 손해입니다.
x64에는 곱의 상/하위를 동시에 뽑아주는 인트린(예: _mulx_u64) 계열이 있고, 이를 조합하면 필요한 부분만 빠르게 조립할 수 있습니다.1 핵심 전략은 “필요한 크기만 만들고, 넘치는 캐리는 과감히 버린다(잘 정의된 wrap-around)”입니다. 고정 폭 정수의 세계에서는 이게 오히려 자연스럽고, 최적화도 더 잘 먹습니다.
비교 연산: XOR로 동등 비교, borrow로 크기 비교
동등 비교는 의외로 “분기 없는” 방식이 가장 깔끔합니다. hi와 lo를 각각 XOR한 뒤 OR로 합치면, 결과가 0인지 여부만 보면 됩니다. 이렇게 하면 조건 분기 예측 실패 같은 변수를 줄일 수 있고, 어셈블리도 단순해집니다.1
크기 비교(a < b)는 상위 limb부터 비교하는 정석이 있지만, 또 다른 실전 트릭이 있습니다. a - b를 했을 때 보로우가 발생하면 a < b입니다. 즉, _subborrow_u64의 최종 보로우 플래그가 곧 비교 결과가 됩니다.1 “비교를 위해 비교하지 말고, CPU가 잘하는 빼기를 시켜서 플래그를 읽는다”는 느낌이라, 생성 코드가 간결해지는 편입니다.
플랫폼별 현실 체크: MSVC·GCC·Clang·ARM에서의 주의점
MSVC는 __uint128_t가 없거나 제약이 크기 때문에, 이런 u128 직접 구현이 특히 실용적입니다. 반대로 GCC/Clang은 __uint128_t가 잘 되지만, 여전히 “내가 원하는 연산만 정확히, 예측 가능한 코드로” 가져가고 싶을 때 직접 구현이 의미가 있습니다.1
AArch64(ARM 64비트)로 가면 x64 인트린을 그대로 쓸 수는 없습니다. 대신 ARM이 제공하는 캐리/보로우 계열 내장 함수(또는 컴파일러 빌트인)를 사용하거나, 컴파일러가 패턴을 알아서 최적화하도록 코드를 작성하는 쪽으로 접근합니다. 요지는 하나입니다. “플래그 기반 연산을 쓰면 CPU가 가장 편하게 계산한다”는 철학만 유지하면, 플랫폼이 바뀌어도 설계 자체는 오래 갑니다.1
나눗셈은 왜 어려울까: 직접 구현은 가능하지만, 설계로 피하는 게 이득
덧셈/뺄셈/곱셈은 CPU에 ‘딱 맞는’ 명령이 있어서 빠르게 끝나지만, u128 나눗셈은 이야기가 다릅니다. 내장형을 써도 라이브러리 호출로 빠지는 경우가 흔하고, 직접 구현도 보통 이진 롱 디비전(shift-subtract) 계열로 가야 해서 속도 한계가 명확합니다.1
그래서 고성능 분야에서는 “division-free” 설계를 권장합니다. 예를 들어 exact predicate(정확 판정)나 기하 연산에서는, 가능하면 곱셈·비교·조건 없는 누산 중심으로 문제를 재구성하는 식이죠. 나눗셈이 꼭 필요하면 구현하되, 성능 목표를 덧셈/곱셈 수준으로 기대하면 실망할 확률이 큽니다.1
시사점을 정리하면 이렇습니다. u128을 u64 두 개로 구현하는 건 단순히 “내장형이 없어서 어쩔 수 없이” 하는 대안이 아니라, 고정 폭 정수라는 강점을 살려 성능과 예측 가능성을 동시에 가져오는 패턴입니다.1 특히 캐리/보로우를 인트린식으로 다루면 컴파일러가 기계어를 예쁘게 뽑아주기 쉬워서, 결과적으로 내장형에 가까운 최적화를 얻습니다.
그리고 한 번 이 패턴에 익숙해지면, 192/256비트 같은 더 큰 정수도 “limb를 늘리는 방식”으로 자연스럽게 확장됩니다. BigInt가 꼭 필요하지 않은 문제라면, 오히려 고정 폭이 더 빠르고 단단합니다.