본문 바로가기
알고리즘/필기

연속한 수의 XOR sum

by 유시은 2020. 12. 25.
ll xorSum(ll n) {
	int m = n % 4;
	if (m == 0) return n;
	if (m == 1) return 1;
	if (m == 2) return n + 1;
	return 0;
}

 

1부터 n까지의 수의 XOR sum은 위와 같다.

 

자세한 내용은 여기에서 볼 수 있다.

 

 

ll xorSum(ll l, ll r) {
	return xorSum(l - 1) ^ xorSum(r);
}

 

구간 [L : R] 의 xor 합 역시 같은 두 수를 xor 하면 0이 된다는 사실을 이용하여 구할 수 있다.

'알고리즘 > 필기' 카테고리의 다른 글

연속한 수의 XOR sum  (0) 2020.12.25
치킨 쿠폰  (0) 2020.11.25
유니온 파인드  (0) 2020.09.11
Z  (0) 2020.08.15

태그

댓글0