1부터 n사이의 홀수의 합을 O(1)로 구하는 방법 ( C++ 최적화 기법 )

갑자기 생각나서 만들어보았습니다.
솔직히 for문으로 1부터 n까지 순회하면서 홀,짝수인지 판별하는것은 구현하기 매우 쉽죠.
하지만, 이랬을때 단점이 n의 수가 커질수록 그 연산시간은 n의 크기에 비례해서 증가한다는 점입니다.
 
우리는 n의 크기에 영향을 받지않고 항상 같은(짧은)속도로 연산을 하는 방법을 의논하는겁니다.
 

1부터 n까지의 홀수의 합을 O(1)로 구하는 방법

#include <iostream>

using bint = std::int64_t;

bint Get_1toN_in_O1(bint n){
	bint ncore, ncycle, result;
	
	n -= (n & 1) ? 0 : 1;
	ncore = ((n + 1) >> 1);
	ncycle = (ncore >> 1);
	result = (ncycle * (n + 1)) + (ncore & 1 ? ncore : 0);
	
	return result;
}

bint Get_1toN_in_On(bint n){
	bint result;
	
	result = 0;
	
	for(int i = 1;i <= n; ++i) {
		if ((i % 2) != 0){
			result += i;
		}
	}
	
	return result;
}

int main() {
	bint n;
	std::cin >> n;
	
	std::cout << "O(1) : " << Get_1toN_in_O1(n) << std::endl;
	std::cout << "O(n) : " << Get_1toN_in_On(n) << std::endl;
}

 
우선 우리가 이번에 설명할 함수는 Get_1toN_in_O1 입니다.
먼저 우리가 1부터n 사이의 홀수의 합을 구하기 위해서는 3개의 수가 필요합니다.
첫번째는 n이죠.
두번째는 수열을 나열했을때, 제일 가운데에 위치한 수입니다.
세번째는 1과 n을 더한후 몇번반복해서 더해야 1부터n까지의 총합을 구할수있는지, 그 회전수(cycle)를 알아야 합니다.
 
저는 이 방법을 가우스의 1 + ... + 100 = 5050 이 공식에서 힌트를 받았어요.
먼저 우리는 홀수의 합을 구할것이기 때문에, n이 짝수가 들어올때는 1을 뺴줍니다.
 
그다음 ncore는 수열을 나열했을때, 제일 가운데에 위치한 수이므로,  n+1에서 2를 나눠줍니다.
1을 right shift연산을 하게되면 2가나눠지며, 비트연산을 하는이유는 연산속도가 증가하기 때문입니다.
 
이제 ncore를 반으로 나누게되면 몇번 회전해야하는지 그 수인 ncycle이 나옵니다.
만약 n이 5라면
ncycle은 1이 되겠죠.
왜냐하면
1. (1 + 5)
 
또 n이 7이라면
ncycle은 2가 되겠죠.
1. (1 + 7)
2. (3 + 5)
 
자....
이제 (n + 1)값을 ncycle만큼 곱해준다음, 만약? 가운데에 위치한 수 ncore이 홀수라면 더해줍니다.
이로써 1부터n사이에 위치한 모든 홀수의 합을 구할수있습니다.
 
끝.
 

---