BOJ - 25306 ) 연속 XOR

 

---

https://www.acmicpc.net/problem/25306

25306번: 연속 XOR

---

XOR연산(결합,교환) 특성에 의해 1-(A-1) 까지와 1-B까지 숫자에 대한 XOR이 

A-B까지 XOR이 같게된다.

 

첫번째 자리를 제외한 비트를 나열해보면, 모두 주기를 띄고있다.( 0011 00001111 ... )

따라서 2^N으로 비트를 밀면서 해당 번째가 00에속하는지 11에 속하는지 먼저 판단하고,

11영역에 속한다면, 해당 1의 누적개수가 짝수개면 0 홀수개면 1로 비트를 바꾸어준다.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long n = Long.parseLong(st.nextToken());
		long m = Long.parseLong(st.nextToken());
		
		System.out.println((XOR(n-1)
				 ^XOR(m)));
	}

	private static long XOR(long num) {
		long answer =0;
		if(num%2==1) {
			if( ((num+1)/2)%2==1) {answer++;}
		} else {
			if( ((num)/2)%2==1) {answer++;}
		}
		
	 for(long i=1;i<=num;i*=2) {
			if( (num%(i*2))>=i&&
					 (((num%(i*2))&1)==0) ) {
				answer ^=i;
			}
		
		}
		return answer;
	}
}

---