KOL16B - Editorial



Editorialist: Soumik Sarkar




Binary, Bitwise operations


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.


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.


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 can be found here.