[Java] long보다 더 큰 수를 다룰 수 있다고?(BigInteger)

https://www.acmicpc.net/problem/2824 문제를 풀다가 `BigInteger`를 처음 만났다. 일반적으로 `int`, `long`으로 충분하지만, 매우 큰 수를 다뤄야 하는 경우가 있어 정리해보려고 한다.

---

BigInteger란?

`BigInteger`는 불변의 임의 정밀도 정수로 자바의 기본 정수형은 메모리 크기가 고정되어 있어 이보다 더 큰 값들을 다를 때 사용한다.

범위

• `int` (4 byte): -21억 ~ 21억
• `long` (8 byte): -922경 ~ 922경
• `BigInteger`: -2^(Integer.MAX_VALUE) ~ 2^(Integer.MAX_VALUE) (약 6억 자리 이상)

기본 정수형들은 JVM에서 Stack에 저장되지만 `BigInteger`은 참조값이 Stack에 저장되고 실제 객체는 Heap에 저장된다. 

다음은 `BigInteger`의 실제 내부 구조이다. 사실 더 많은 필드들이 있지만 다 캡쳐하기가 어려워 여기까지만 캡쳐했다. `BigInteger`는 최소 48바이트를 필요로 하고 수가 커질 수록 +α이다. 

구성 요소

• BigInteger 객체 헤더: 12~16바이트 (64비트 JVM 기준)
• signum: 4바이트
• mag 배열 참조: 4바이트
• int[] 배열 객체: 
  • 배열 헤더: 12~16바이트
  • 배열 길이 필드: 4바이트
  • 최소 1개의 `int` 데이터: 4바이트

크기가 커질 때 숫자가 커지면 `int` 배열 크기가 늘어난다. (int 하나 = 32비트 = 약 10자리(2^32 ≈ 42억), 32진법이라고 생각하면 된다. 32비트 연산을 하는 이유는 CPU가 32비트 연산에 최적화되어 있기 때문이다. )

• 1자리 수 (예: 5): 약 48바이트
• 10자리 수: 약 48바이트 (int 1개로 충분)
• 20자리 수: 약 52바이트 (int 2개 필요)
• 100자리 수: 약 68바이트 (int 4개 필요)
• 1000자리 수: 약 188바이트 (int 34개 필요)

메모리 ≈ 48 + (필요한 int 개수 × 4) 필요한 int 개수 ≈ ⌈10진수 자릿수 / 9.6⌉

---

BigInteger의 특징

무한한 크기

`BigInteger`는 내부적으로 `int[]배열을 사용해 값을 저장한다. 따라서 컴퓨터의 RAM이 허용하는 한, 이론적으로 크기에 제한이 없는 정수를 저장하고 연산할 수 있다.

불변성

`String` 클래스와 마찬가지로 `BigInteger`는 불변객체이다. 한 번 생성된 `BigInteger` 객체의 값은 절대 변하지 않는다. 덧셈이나 뺄셈 같은 연산을 수행하면, 기존 값이 바뀌는 것이 아니라 계산 결과가 담긴 새로운 `BigInteger` 객체가 반환된다.

---

BigInteger의 사용법

`BigInteger`는 클래스이므로, 사칙연산 기호(+, -) 대신 메서드를 사용해야 한다.

선언 및 생성

import java.math.BigInteger;

BigInteger bigNum1 = new BigInteger("123456789123456789123456789");
BigInteger bigNum2 = BigInteger.valueOf(100); // long 범위 내라면
BigInteger binaryNum = new BigInteger("1010", 2); // 10진수 외의 진수 표현 (예: 2진수)

// 자주 쓰는 0, 1, 10은 상수로 제공
BigInteger zero = BigInteger.ZERO;
BigInteger one = BigInteger.ONE;
BigInteger ten = BigInteger.TEN;

연산

BigInteger a = new BigInteger("100");
BigInteger b = new BigInteger("20");

// 사칙연산
BigInteger sum = a.add(b);           // 덧셈
BigInteger diff = a.subtract(b);     // 뺄셈
BigInteger product = a.multiply(b);  // 곱셈
BigInteger quotient = a.divide(b);   // 나눗셈
BigInteger remainder = a.remainder(b); // 나머지
BigInteger power = a.pow(3);         // 거듭제곱

// 비교
int compare = a.compareTo(b);  // a > b이면 1, a == b이면 0, a < b이면 -1
boolean equal = a.equals(b);

// 최댓값/최솟값
BigInteger max = a.max(b);  // 200
BigInteger min = a.min(b);  // 100

// 최대공약수
BigInteger gcd = a.gcd(b);  // 20

// 모듈러 연산
BigInteger base = new BigInteger("2");
BigInteger exp = new BigInteger("10");
BigInteger mod = new BigInteger("1000");
base.modPow(exp, mod);  // 2^10 mod 1000 = 24
                        // 큰 수 거듭제곱 계산에 유용!

a.modInverse(b);  // a의 모듈러 곱셈 역원

자료형 변환

BigInteger big = new BigInteger("123456789");

// 기본 자료형으로 변환 (범위 초과 시 잘림!)
big.intValue();     // int로 변환
big.longValue();    // long으로 변환
big.floatValue();   // float으로 변환
big.doubleValue();  // double으로 변환

// 안전한 변환 (범위 검사)
big.intValueExact();   // int 범위 벗어나면 ArithmeticException
big.longValueExact();  // long 범위 벗어나면 ArithmeticException

// 문자열 변환
big.toString();        // "123456789" (10진수)
big.toString(2);       // "111010110111100110100010101" (2진수)
big.toString(16);      // "75bcd15" (16진수)

비트 연산

BigInteger a = new BigInteger("15");  // 1111 (2진수)
BigInteger b = new BigInteger("10");  // 1010 (2진수)

// 비트 논리 연산
a.and(b);     // 1010 = 10 (AND)
a.or(b);      // 1111 = 15 (OR)
a.xor(b);     // 0101 = 5 (XOR)
a.not();      // -16 (NOT, 2의 보수)

// 비트 시프트
a.shiftLeft(2);   // 15 << 2 = 60
a.shiftRight(2);  // 15 >> 2 = 3

// 비트 개수
a.bitCount();     // 1의 개수 = 4
a.bitLength();    // 비트 길이 = 4

// 특정 비트 확인/설정
a.testBit(0);     // 최하위 비트가 1인가? true
a.setBit(5);      // 5번 비트를 1로
a.clearBit(0);    // 0번 비트를 0으로
a.flipBit(1);     // 1번 비트 반전

소수 관련

// 소수 생성 (확률적 소수)
BigInteger prime = BigInteger.probablePrime(100, new Random());

// 소수 판별 (확률적)
BigInteger num = new BigInteger("17");
num.isProbablePrime(100);  // true

---

주의사항

속도 저하

`BigInteger`는 기본 타입보다 속도가 느리다. 단순히 큰 숫자가 필요하다고 해서 무조건 사용하는 것은 좋지 않다. 

메모리 사용

객체 생성이 빈번하게 일어나고(불변성이므로), 내부 배열 크기도 유동적이므로 메모리 관리에 신경 써야 한다.

비교 연산

객체이므로 `==` 연산자가 아닌 `.equals()`나 `.compareTo()`를 사용해야 값을 비교할 수 있다.