### PROBLEM LINK:

Editorialist: Soumik Sarkar

### DIFFICULTY:

CAKEWALK

### PREREQUISITES:

Binary, Bitwise operations

### PROBLEM:

A procedure to merge two numbers, each less than 30000, into one number is provided. Given a list of such merged numbers, find a way to recover the two original numbers from each merged number.

### QUICK EXPLANATION:

Each pair of number is combined into one number `m`

. Obtain the two original numbers from each new number as `m & 0xffff`

and `m >> 16`

.

### EXPLANATION:

The procedure to merge two numbers is described as such

int encodeInteger(int x, int n){ n = n<<(1<<(1<<(1<<1))); x = x | n; return x; }

We can simplify `n = n<<(1<<(1<<(1<<1)))`

to `n = n << 16`

. The next step is `x = x | n`

. So, put together, the numbers `x`

and `n`

are merged to get the number `x | (n << 16)`

. In other words, the number `x`

is kept in the lower 16 bits, and the number `n`

is bit shifted left by 16 to occupy the next 16 bits. These are then bitwise OR-ed together.

For example:

Let `x = 30000`

, which is `111010100110000`

in binary

Let `n = 12321`

, which is `11000000100001`

in binary.

Shifting `n`

left by 16 bits, we get `110000001000010000000000000000`

.

Bitwise OR-ing`, 000000000000000111010100110000 OR 110000001000010000000000000000 ------------------------------ 110000001000010111010100110000`

The OR-ed result turns out to be `807499056`

in this case.

It is possible to obtain the original numbers in many ways.

Let `m`

be the merged number. Then,

`x = m & 0b1111111111111111`

, or

`x = m & 0xffff`

, or

`x = m & ((1 << 16) - 1)`

All of these do the same thing, they use bitwise AND to keep only the lowest 16 bits of `m`

, which we know is `x. 110000001000010111010100110000 AND 000000000000001111111111111111 ------------------------------ 000000000000000111010100110000`

To find `n`

, the simplest way is

`n = m >> 16`

.

Shifting `m`

16 bits to the right removes the lower 16 bits and only the value of `n`

remains`. 110000001000010111010100110000 ↓ SHIFT RIGHT BY 16 ↓ 000000000000000011000000100001`

### EDITORIALIST’S SOLUTION:

Editorialist’s solution can be found here.