KOL16B - Editorial

acm16kol
bitwise
cakewalk
editorial
kol16b

#1

PROBLEM LINK:

Practice
Contest

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.