 # KOL16B - Editorial

Editorialist: Soumik Sarkar

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.

2 Likes