Bit Manipulation XOR tricks
115. XOR of All Numbers in a Range
Medium
You are given two integers left and right. Return the XOR of every integer from left to right,
both included: left ^ (left + 1) ^ … ^ right.
XOR (^) compares two numbers bit by bit. Each bit of the result is 1 where the two bits differ and 0
where they are the same. For example, 6 ^ 3 is 110 ^ 011 = 101, which is 5.
Example 1
Input: left = 3, right = 9
Output:
2Explanation: 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9. Going left to right, the running result is 3, 7, 2, 4, 3, 11 and
finally 2.
Example 2
Input: left = 12, right = 12
Output:
12Explanation: The range holds one number, so the answer is that number.
Example 3
Input: left = 5, right = 1000000000000000
Output:
1000000000000004Check your understanding
Work out the answer for this input before you write any code.
left = 1, right = 4
Constraints
1 ≤ left ≤ right ≤ 1015
Clarifying questions
What you would ask an interviewer before writing any code.