오늘의 한 마디
막상 공식을 알고 나니까, 대회에서 사람들이 왜 그렇게 빨리 풀었는지 알 수 있었다.

• Baekjoon 문제 링크
• 2022 연세대학교 미래캠퍼스 슬기로운 코딩생활 Open Contest의 C번 문제입니다.
• 솔브닥 기준 난이도 : 골드 4

문제

준원이는 다음과 같이 $A$에서 $B$까지의 자연수들을 나열했다.

$A, A+1, A+2, \dots, B-2, B-1, B$ 

이 수들에 모두 비트 XOR을 취한 값을 구하라.

입력

두 자연수 $A$, $B$가 공백을 사이에 두고 주어진다.

출력

 $A$ 이상 $B$ 이하인 모든 자연수들을 XOR한 값을 구하여라.

제한

 $1 ≤ A ≤ B ≤ 1\,000\,000\,000\,000\,000\,000 = 10^{18}$ 

예제 입력 1

3 4

예제 출력 1

7

3에서 4까지의 자연수들은 3과 4로, 두 개 존재한다.
두 수를 XOR한 값은 3 XOR 4 = 7 이다.

예제 입력 2

3 5

예제 출력 2

2

3에서 5까지의 자연수는 3, 4, 5로, 세 개 존재한다.
세 수를 XOR한 값은 (3 XOR 4) XOR 5 = 7 XOR 5 = 2 이다.

---

발상

Try #1 : 그대로 구현

import sys
input = lambda: sys.stdin.readline().rstrip()

A, B = map(int, input().split())

answer = A
for i in range(A+1, B+1):
    answer ^= i
print(answer)

당연히 시간 초과

Try #2 : 이진수로 변환하여 비트 별로 XOR 해주기

import sys
input = lambda: sys.stdin.readline().rstrip()

A, B = map(int, input().split())

answer = [0]*100
for i in range(A, B+1):
    raw = bin(i)[2:]
    raw = raw[::-1]
    for idx in range(len(raw)):
        if raw[idx] == '1':
            answer[idx] = 1 if answer[idx] == 0 else 0

answer = answer[::-1]
answer = '0b'+ ''.join(map(str, answer))
print(int(answer, 2))

나름 XOR의 성질을 이용했지만, 역시 시간 초과였다.
시간 복잡도가 O(n^2)라서 실질적으로 시간 복잡도를 늘린 꼴이 아닌가 싶다.

대회 당시에는 못 풀었다.

끝나고 후기를 보고 이와 완전히 똑같은 문제를 찾을 수 있었다.
백준 10464. XOR

문제 : S에서 F까지의 모든 정수를 XOR한 값은 무엇일까?

해설

[A, B]의 연속 XOR 값은 [1,A-1]의 연속 XOR ^ [1, B]의 연속 XOR 한 값과 같다!

[1, n]의 연속 XOR에는 놀랍게도 특정한 규칙이 있다.

다른 사람들은 이걸 어떻게 즉석에서 알았을까..? 싶다

---

풀이

import sys
input = lambda: sys.stdin.readline().rstrip()

A, B = map(int, input().split())

def f(n):
    start = n//4 * 4
    answer = 0
    for i in range(start, n+1):
        answer ^= i
    return answer

print(f(A-1) ^ f(B))