LittleElephantAndXor | Topcoder Archive

Problem Statement

Little Elephant from the Zoo of Lviv likes integers.

You are given three ints A, B and C. Return the number of ordered pairs (X,Y) of integers such that 0 <= X <= A, 0 <= Y <= B, and the value (X XOR Y) is less than or equal to C.

Definition

Class:: LittleElephantAndXor
Method:: getNumber
Parameters:: int, int, int
Returns:: long
Method signature:: long getNumber(int A, int B, int C)
(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.

Constraints

A, B and C will each be between 1 and 1,000,000,000 (109), inclusive.

Examples

```
2
```
```
2
```
```
1
```
```
Returns: 5
```
There are 9 possible pairs in this case: 0 XOR 0 = 0 0 XOR 1 = 1 0 XOR 2 = 2 1 XOR 0 = 1 1 XOR 1 = 0 1 XOR 2 = 3 2 XOR 0 = 2 2 XOR 1 = 3 2 XOR 2 = 0 Among them, only 5 have XOR less than or equal to 1. Note that (0,1) and (1,0) are two different pairs.
```
4
```
```
7
```
```
3
```
```
Returns: 20
```
```
10
```
```
10
```
```
5
```
```
Returns: 57
```
```
774
```
```
477
```
```
447
```
```
Returns: 214144
```

1000000000

1000000000

500000000

Returns: 468566946385621507

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)2024, Topcoder, Inc. All rights reserved.