[Play with Java] 자바에서 오버플로우 없이 2개의 INT 평균 구하기

(a + b) / 2

 더해서 2로 나누는 것은 오버플로우가 발생한다.

int a = 1_894_234_753;
int b = 1_882_312_653;
System.out.println((a+b)/2); // -259209945

 

low + (high - low) / 2

둘중에 큰 수를 알면 두 값의 차이를 작은 수에 더해서 2로 나누는 것도 가능하다.

int low = 1_894_234_753;
int high = 1_882_312_653;
System.out.println(low + (high-low)/2); // 1888273703

 

(a / 2) + (b / 2) + (a & b & 1)

어떤게 큰 수인지 몰라도 가능한 알고리듬은 2016년에 특허가 만료되었다.

• 홀수 + 홀수일 경우 1이 생략되기 때문에둘 다 홀수일 경우 1이 찍히는 a&b&1을 더해준다.

int a = 1_894_234_753;
int b = 1_882_312_653

// 홀수 + 홀수일 경우 1이 생략됨 
// a&b&1 -> 둘 다 홀수일 경우 1
System.out.println(a/2+b/2 + a&b&1); // 1888273703

 

(a & b) + (a ^ b) / 2

SWAR : SIMD within a register

13: 1101

14: 1110 

a&b + a^b = 1100 + 0011 = 1111 = 14

a&b  + a^b/2 = 1100 + 0001 = 1101 = 13

 

14 : 1110

12 : 1100

a&b + a^b 1100+0010 = 1110 = 14

a&b + a^b/2 = 1100+0001 = 1101 = 13

int a = 1_894_234_753;
int b = 1_882_312_653;
System.out.println((a&b) + (a^b)/2); // 1888273703

 

 ((long)a + b) / 2

컴파일러가 64비트를 지원한다면 캐스팅. 이게 젤 편하긴 하다.

int a = 1_894_234_753;
int b = 1_882_312_653;
System.out.println(((long)a+b)/2); // 1888273703

 

ArrayList capacity 증가하는 방식

Java 6

(oldCapacity * 3) / 2 + 1  -> *3 에서 overflow가 발생한다.

 

Java 7 이후

oldCapacity + (oldCapacity >> 1)로 변경

---

참고

On finding the average of two unsigned integers without overflow