나머지 연산: 음수의 나머지는 언어마다 다르다

이미지 캐러셀의 "다음"과 "이전" 버튼을 AI에게 짜 달라고 하면 이런 코드가 자주 나온다.

const next = () => setIndex(i => (i + 1) % slides.length)
const prev = () => setIndex(i => (i - 1) % slides.length)

"다음"은 끝까지 가면 처음으로 잘 돌아온다. 그런데 첫 슬라이드에서 "이전"을 누르면 화면이 빈다. index가 -1이 되어 slides[-1]이 undefined이기 때문이다. 같은 식을 Python으로 옮기면 마지막 슬라이드로 잘 넘어간다. 같은 %가 왜 언어마다 다른 답을 낼까? 이 Unit은 나눗셈의 몫과 나머지를 정의부터 다시 보고, 나머지가 실무 코드에서 쓰이는 자리와 음수·오버플로에서 생기는 차이를 본다.

몫과 나머지: 시계 산수

1const m = 32for (const a of [4, 3, 2, 1, 0, -1, -2, -3, -4]) {3  console.log(`${a} ÷ ${m} → 몫 ${Math.trunc(a / m)}, 나머지 ${a % m}`)4}

4 ÷ 3 → 몫 1, 나머지 1
3 ÷ 3 → 몫 1, 나머지 0
2 ÷ 3 → 몫 0, 나머지 2
1 ÷ 3 → 몫 0, 나머지 1
0 ÷ 3 → 몫 0, 나머지 0
-1 ÷ 3 → 몫 0, 나머지 -1
-2 ÷ 3 → 몫 0, 나머지 -2
-3 ÷ 3 → 몫 -1, 나머지 0
-4 ÷ 3 → 몫 -1, 나머지 -1

먼저 양수부터 정리하자. 7을 3으로 나누면 3이 두 번 들어가고 1이 남는다. 이때 2를 몫(quotient), 1을 나머지(remainder)라고 한다.

$7 = 3 \times 2 + 1$

"7은 3을 두 번 더하고 1을 더한 수"라고 읽는다. 일반적으로 적으면 이렇다.

$a = m \times \text{몫} + \text{나머지}$

a는 나뉘는 수(dividend), m은 나누는 수(divisor)다. 양수끼리라면 나머지는 늘 0 이상이고 m보다 작다. 3으로 나눈 나머지는 0, 1, 2 셋 중 하나다. 나머지를 구하는 계산을 나머지 연산(modulo)이라고 하고, 코드에서는 %, 수학에서는 mod로 적는다. 7 % 3과 $7 \bmod 3 = 1$은 같은 계산이다.

나머지가 늘 0부터 m − 1 사이라는 성질 때문에, 나머지 연산은 "끝까지 가면 처음으로 돌아오는" 셈에 맞는다. 시계가 대표적이다. 12시간 시계에서 10시의 5시간 뒤는 15시가 아니라 3시다.

$15 \bmod 12 = 3$

"15를 12로 나눈 나머지는 3"이라고 읽는다. 12를 넘은 만큼만 남긴다. 25시간 뒤라면 25 ÷ 12 = 몫 2, 나머지 1이라 시곗바늘은 두 바퀴 돌고 한 칸 더 간다.

요일도 같다. JavaScript의 getDay()는 일요일을 0, 월요일을 1, …, 토요일을 6으로 돌려준다(MDN: Date.prototype.getDay). 오늘이 수요일(3)이면 100일 뒤의 요일 번호는 이렇다.

$(3 + 100) \bmod 7 = 5$

103 = 7 × 14 + 5라서 나머지는 5, 금요일이다. 일주일이 14번 돌고 다섯 칸 더 간 셈이다.

나머지의 쓰임: 짝홀, 돌아가는 인덱스, 버킷, 페이지

실무 코드에서 %가 나오는 자리는 대부분 넷 중 하나다.

해시 버킷 줄은 해시 테이블(hash table)이 쓰는 계산이다. 해시 함수(hash function)가 키를 아주 큰 정수로 바꾸면, 그 수를 버킷(bucket) 수로 나눈 나머지가 저장할 칸 번호가 된다. 자세한 구조는 해시 테이블 노트에 있다.

페이지 계산에서는 몫과 나머지를 함께 쓴다. 항목 37개를 한 쪽에 10개씩 보여 주면 37 ÷ 10 = 몫 3, 나머지 7이라 꽉 찬 쪽 3개와 7개짜리 쪽 하나, 모두 4쪽이다. 쪽 수는 나머지가 0이 아니면 하나를 더해야 해서 Math.ceil(37 / 10), 곧 올림으로 구한다.

음수의 나머지: 나뉘는 수의 부호냐, 나누는 수의 부호냐

나뉘는 수가 음수일 때 두 언어는 몫을 다르게 정한다. -1 ÷ 3 = -0.333…에서 몫을 정수로 만들 때, JavaScript는 소수 부분을 버려 0 쪽으로 붙이고(-0.333… → 0), Python은 내림해서 더 작은 정수로 붙인다(-0.333… → -1). 몫이 다르면 앞의 식 a = m × 몫 + 나머지를 맞추는 나머지도 달라진다.

$-1 = 3 \times 0 + (-1) \qquad -1 = 3 \times (-1) + 2$

왼쪽이 JavaScript, 오른쪽이 Python이다. 둘 다 식으로는 맞다. 결과적으로 JavaScript %의 나머지는 늘 나뉘는 수의 부호를 따르고(MDN: 나머지 연산자), Python %의 나머지는 늘 나누는 수의 부호를 따른다(Python 문서: 이항 산술 연산).

//는 Python에서 "나눈 뒤 내림한 몫"을 구하는 연산자다. 그래서 Python의 %는 //와 짝이고, JavaScript의 %는 Math.trunc와 짝이다. JavaScript에서 Math.floor(a / m)로 몫을 구하면서 나머지를 %로 구하면 둘이 맞지 않는다. Math.floor(-1 / 3)은 -1인데 -1 % 3도 -1이라서, 3 × (-1) + (-1) = -4가 되어 -1로 돌아오지 않는다.

캐러셀의 "이전" 버튼은 바로 이 차이에 걸린다. i = 0에서 (0 - 1) % 4는 JavaScript에서 -1이다. 고치는 방법은 나머지에 나누는 수를 한 번 더한 뒤 다시 나머지를 구하는 것이다. MDN도 JavaScript에서 나누는 수의 부호를 따르는 나머지를 얻으려면 ((n % d) + d) % d를 쓰라고 안내한다.

1const n = 42const mod = (a: number, b: number) => ((a % b) + b) % b3let i = 04for (const click of ['prev', 'prev', 'next', 'next', 'next']) {5  i = click === 'next' ? mod(i + 1, n) : mod(i - 1, n)6  console.log(`${click} → ${i}번 슬라이드`)7}

prev → 3번 슬라이드
prev → 2번 슬라이드
next → 3번 슬라이드
next → 0번 슬라이드
next → 1번 슬라이드

슬라이드가 4장이면 0번에서 "이전"을 누를 때 -1 % 4는 -1이지만, 4를 더하면 3이고 3 % 4는 3이라 마지막 슬라이드로 간다. 나머지가 처음부터 0 이상이었다면 d를 더해도 다시 d로 나누므로 결과가 바뀌지 않는다.

오버플로: 32비트는 2³²로 나눈 나머지

나머지는 수가 담을 수 있는 범위를 넘을 때도 나온다. 네 자리 주행 거리계는 9999 다음에 0000을 보여 준다. 다섯째 자리를 담을 칸이 없어서 10000으로 나눈 나머지만 남는 것이다. 정해진 자리 수를 넘어 처음으로 돌아가는 일을 오버플로(overflow)라고 한다.

컴퓨터의 정수도 같다. 0 또는 1 하나를 비트(bit)라고 하는데, 비트 32개로는 2를 32번 곱한 가짓수, 2³² = 4,294,967,296개의 값을 담는다. 32비트를 넘는 자리를 버리고 아래 32비트만 남기는 일은 2³²로 나눈 나머지를 구하는 것과 같다.

$x \bmod 2^{32}$

"x를 2³²로 나눈 나머지"라고 읽는다. 2³² + 5는 2³²로 나누면 나머지가 5라서 5가 된다.

음수도 담는 부호 있는 정수(signed integer)로 32비트를 쓰면 이 2³²가지를 -2³¹(-2,147,483,648)부터 2³¹ − 1(2,147,483,647)까지의 범위에 나눠 쓴다. 나머지가 2³¹ 이상이면 2³²를 빼서 음수로 읽는다. Unit 1의 4비트 표에서 1000을 8이 아니라 −8로 읽은 것과 같은 규칙이다(Unit 1 6절). 1000은 그대로 읽으면 8인데, 맨 위 자리를 +8 대신 −8로 세면 16(= 2⁴)만큼 작아져 8 − 16 = −8이 된다. 32비트에서는 맨 위 자리가 +2³¹ 대신 −2³¹이라 2³²를 빼는 것이다. 그래서 2³¹ − 1에 1을 더하면 맨 끝 음수 -2³¹로 넘어간다. 가장 큰 수 다음이 가장 작은 수가 되는 것이, 주행 거리계의 9999 다음이 0000인 것과 같다.

JavaScript의 수는 원래 32비트 정수가 아니라, 정수와 소수를 한 형식(64비트 부동소수점)에 담는 number 하나다(그 형식의 속은 『한입 CS』 0장). 하지만 비트 연산자 |, &, >> 등은 피연산자를 부호 있는 32비트 정수로 바꾼 뒤 계산한다(MDN: 비트 OR). 그래서 x | 0은 "x를 32비트 정수로 되돌리기"로 자주 쓰인다.

Python의 정수는 크기 제한이 없다(Python 문서: 숫자 형). 2³¹ − 1에 1을 더하면 그냥 2³¹이다. 다른 언어의 32비트 계산을 Python으로 옮길 때는 % 2**32처럼 나머지를 직접 적어야 한다. 이 차이는 장 끝 보너스 문제에서 다시 본다.

확인: 나머지 코드에서 틀린 줄 찾기

검토 기준은 앞 절에 다 나왔다. 쪽 수를 셀 때 나머지가 남는 경우를 넣었는가(2절), %마다 나뉘는 수가 음수일 수 있는가(3·4절)를 묻는다.

이 Unit이 쓰이는 곳

• 『한입 알고리즘』 1장 해시: 해시 함수 모델을 key % size(버킷 수로 나눈 나머지)로 둔다. 2, 7, 12, 17처럼 5로 나눈 나머지가 같은 키가 한 버킷에 몰리는 충돌도 나머지로 설명한다.
• 『한입 알고리즘』 6장 이분 탐색: 함정 찾기 뒤 설명에서 (lo + hi) >> 1이 32비트 정수로 계산되어 2³¹ 이상이 음수로 읽힌다. 이 Unit의 "오버플로" 절에서 본 일이다.
• 『한입 CS』 0장 숫자는 비트다: JavaScript 수가 정수를 2⁵³까지는 빈틈없이 담지만 2⁵³ + 1은 2⁵³으로 반올림해 버려서, 안전한 정수(Number.MAX_SAFE_INTEGER)가 2⁵³ − 1까지인 이유가 나온다(Unit 1 2절). Math.imul이 필요한 이유(곱이 2⁵³를 넘음)와 이어진다.
• 『한입 CS』 5장 메모리 계층: 캐시 모델에서 칸 번호를 2로 나눈 몫이 블록 번호이고, 블록 번호를 캐시 자리 수로 나눈 나머지가 그 블록이 들어갈 자리다.
• 『한입 CS』 7장 HTTP: 함정 찾기 코드가 SHARDS[id % SHARDS.length]로 이미지 id를 서버 셋 중 하나에 나눠 보낸다. 돌아가는 인덱스와 같은 계산이다.

hello → 99162322
polygenelubricants → -2147483648