PROBLEM LINK:
Author: Tasnim Imran Sunny
Tester: Istvan Nagy
Editorialist: Lalit Kundu
DIFFICULTY:
Simple
PREREQUISITES:
bitwise operators, basic maths
PROBLEM:
Given an integer N, Chef wants to find the smallest positive integer M such that the bitwise XOR of M and M+1 is N. If no such M exists output -1.
EXPLANATION:
================
First thing you should while trying to solve this problem is to see how XOR of two consecutive numbers behave. As we know XOR of two same bits is 0 while XOR of two different bits is 1.
Now, let’s say we have a number M and we are going to add 1 to it.
If last(least significant) bit of M is 0(i.e. M is divisible by 2), then M+1 will be exactly same as M except the last bit which will be set. Formally, if M = b_1, b_2, ... , b_n, and b_n == 0, then M+1 is M+1 = b_1, b_2, ... , \bar{b_n}(we denote not of a bit a by \bar{a}). So, M XOR M+1 in this case is going to be 1, because all other bits are same.
What if least significant of M is set? In that case, we have to keep a carry which keeps moving towards significant bits. Now, this carry at any position is at most 1. So, the first position(while moving from least to most significant position) at which a 0 is present in M, our computation will end.
So, we can say that to add 1 to a number M we start from least significant position and keep flipping set bits until we get an unset bit, which we have to set and we are done. Formally, if M = b_1, b_2, ... , b_n, we find largest i \le n such that b_i ==0 and b_j == 1 \forall j>i. We can say that M+1 = b_1, b_2, ..., \bar{b_i}, \bar{b_{i+1}}, \bar{b_{i+2}}, ..., \bar{b_{n}}.
For example, if number is 10111, for adding 1 to it, first we start from right to left and keep flipping bits until we get a not set bit, at the step we set that not set bit, so it will give 11000. Similarly, adding 1 to 10001111 will give 10010000.
Now, notice that all less significant bits beginning from the least significant unset bit(i.e. index i) have been flipped after adding 1 and all other bits remain same. So, XOR of M and M+1 is always of form 2^K-1, where total number of set bits is n-i+1.
Now, for a given N, if its not of form 2^K-1, we can directly say its not possible to find a positive integer M such that the bitwise XOR of M and M+1 is N.
Or else, if there are k set bits in N, then we need to form smallest positive number. You need to observe that for k bits to be set, the index i should be n-k+1 because beginning from index i all bits are set if we take XOR. Now, it is very easy to infer that if there are k set bits in N, then XOR of 2^{k-1}-1 and 2^{k-1} will give us N. For example, N=7 has 3 set bits i.e. N=111(in binary). Now, taking XOR of 11 with 100 will give us N.
Tricky Case:
N=1 is a tricky case here. We remember that for even M, M XOR (M+1) is 1. So, smallest such M is 2.
For checking if a number is of form 2^K-1, you can keep checking bits by repeated division or various bit tricks can also be employed.
