[TopCoder][SRM543] EllysXors 區間XOR
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 long longs L and R. She wants you to find the XOR of all numbers between
L and R, inclusive. |
Definition
|
| |
| Class: |
EllysXors |
| Method: |
getXor |
| Parameters: |
long long, long long |
| Returns: |
long long |
| Method signature: |
long long getXor(long long L, long long R) |
| (be sure your method is public) |
|
| |
| |
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) |
|
| |
|
|
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) |
|
| |
|
|
Returns: 5
|
| The XOR of a single number is the number itself. |
|
|
| 2) |
|
| |
|
| 3) |
|
| |
|
| 4) |
|
| |
|
This problem statement is the exclusive and proprietary property of
TopCoder, Inc. Any unauthorized use or reproduction of this information
without the prior written consent of TopCoder, Inc. is strictly
prohibited. (c)2003, TopCoder, Inc. All rights reserved.
我的想法跟其他人的寫法應該不太一樣, 我是看每個 bit 的個數的奇偶去決定,
你可以很明顯發現最低位的 bit, 週期是 2, 連續一個 1, 次來 4/2, 8/4, 16/8,
然而除了最低位外都是偶數, 其實就沒有那麼重要, 所以只要去查看 L, R 所碰觸的連續 1 個個數即可
#include <cstdio>
using namespace std;
class EllysXors {
public:
long long getXor(long long l, long long r) {
long long ans = 0, i;
for(i = 1; i < 40; i++) {
long long s1 = 0, s2 = 0;
long long tl = l, tr = r;
if((l>>i)&1) {
tl = ((l>>i)<<i)|((1<<i)-1);
if(tl > r)
s1 = r-l+1;
else
s1 = tl-l+1;
}
if((r>>i)&1){
tr = (r>>i)<<i;
if(tr > l)
s2 = r-tr+1;
}
if((s1+s2)&1)
ans |= (long long)1<<i;
}
if(l%2 == 0) l++;
if(r%2 == 0) r--;
if((r-l)/2%2 == 0) ans |= 1;
return ans;
}
};