Connection Status:
Competition Arena > EllysXors

EllysXors

SRM 543 · 2011-11-22 · by espr1t

SRM 543 · 2011-11-22 · by espr1t · Brute Force, Simple Math
Class Name: EllysXors
Return Type: long
Method Name: getXor
Arg Types: (long long, long long)
Problem Statement

Problem Statement

XOR problems became very popular in TopCoder recently. (If you do not know the bitwise operation XOR, see the Notes section for an explanation.) That's why Elly decided to invent one of her own. Fortunately for you, the one she came up with is quite simple. You are given two longs L and R. She wants you to find the XOR of all numbers between L and R, inclusive.

Notes

  • XOR (exclusive or) is a binary operation, performed on two numbers in binary notation. First, the shorter number is prepended with leading zeroes until both numbers have the same number of digits (in binary). Then, the result is calculated as follows: for each bit where the numbers differ the result has 1 in its binary representation. It has 0 in all other positions.
  • For example 42 XOR 7 is performed as follows. First, the numbers are converted to binary: 42 is 101010 and 7 is 111. Then the shorter number is prepended with leading zeros until both numbers have the same number of digits. This means 7 becomes 000111. Then 101010 XOR 000111 = 101101 (the result has ones only in the positions where the two numbers differ). Then the result can be converted back to decimal notation. In this case 101101 = 45, so 42 XOR 7 = 45.
  • One of the ways to calculate the XOR of more than two numbers A1, A2, ..., An is "A1 XOR (A2 XOR (... XOR An))..))". Since the function is commutative and associative, you can also express it as "A1 XOR A2 XOR ... XOR An" and group the operands in any way you like.
  • It can be proved that the answer is always less than 2*R for the given constraints.

Constraints

  • L and R will be between 1 and 4,000,000,000, inclusive.
  • L will be less than or equal to R.
Examples
0)
3
10
Returns: 8

((((((3 XOR 4) XOR 5) XOR 6) XOR 7) XOR 8) XOR 9) XOR 10 = (((((7 XOR 5) XOR 6) XOR 7) XOR 8) XOR 9) XOR 10 = ((((2 XOR 6) XOR 7) XOR 8) XOR 9) XOR 10 = (((4 XOR 7) XOR 8) XOR 9) XOR 10 = ((3 XOR 8) XOR 9) XOR 10 = (11 XOR 9) XOR 10 = 2 XOR 10 = 8.

1)
5
5
Returns: 5

The XOR of a single number is the number itself.

2)
13
42
Returns: 39

A bit larger example.

3)
666
1337
Returns: 0

The answer can be zero.

4)
1234567
89101112
Returns: 89998783

Submissions are judged against all 165 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class EllysXors with a public method long long getXor(long long L, long long R) · 165 test cases · 2 s / 256 MB per case

Submitting as anonymous