Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Bit Manipulation

XOR from 1 to N

Easy · Bit Manipulation · Asked at Amazon, Microsoft, Samsung

Print 1 ^ 2 ^ 3 ^ … ^ n (bitwise XOR).

Input

One integer n.

Output

The XOR value.

Constraints

The result repeats with period 4: n, 1, n + 1, 0 for n % 4 = 0, 1, 2, 3.

Example 1

Input

5

Output

1

Example 2

Input

4

Output

4

Hints

  1. n is up to 10^18 — looping is far too slow. Write out the prefix XORs for n = 1..8 and look for a pattern.
  2. The result depends only on n % 4: n, 1, n + 1, 0 for remainders 0, 1, 2, 3.

Approach

XOR of 1..n repeats with period 4: 1, 3, 0, 4, 1, 7, 0, 8, … For every multiple of 4 (k = 4t), (k) ^ (k+1) ^ (k+2) ^ (k+3) = 0, because the high bits cancel and the low two bits give 0^1^2^3 = 0. So only the last partial block matters. That gives n when n % 4 == 0, 1 when it's 1, n + 1 when it's 2, and 0 when it's 3.

Complexity: O(1) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long ans;
    switch (n % 4) {
        case 0: ans = n; break;
        case 1: ans = 1; break;
        case 2: ans = n + 1; break;
        default: ans = 0;
    }
    cout << ans << "\n";
    return 0;
}

Python solution

n = int(input())
print([n, 1, n + 1, 0][n % 4])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long[] byRemainder = {n, 1, n + 1, 0};
        System.out.println(byRemainder[(int) (n % 4)]);
    }
}

Solve XOR from 1 to N online · All practice problems