XORNUBER - Editorial

PROBLEM LINK:

Practice
Contest

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.

AUTHOR’S, TESTER’S SOLUTIONS:

setter
tester

2 Likes

enjoyed this a lot! nice question on xor for a beginner like me

1 Like

i struggled with input 1 a lot!!

1 Like

CodeChef: Practical coding for everyone whats wrong with this…!

What’s wrong with this solution? CodeChef: Practical coding for everyone

I kept thinking that M would be smaller than n, clearly missing the base case.

How can we say that M should be of the form 2^K-1 ??? @darkshadows

whats wrong with this solution??? plzzz help
https://www.codechef.com/viewsolution/7916726

Shouldn’t the ans for N=1 be M=0 as 0 xor 1 is 1…??

cleverly framed for input 1.
thumps up…

i cant see the submit button not only in this problem but all past contest problem. can anyone tell me why?

@darkshadows @atulshanbhag
what did u meant u said bit tricks can be used to check if the number is of the form 2^k - 1

please help me to find error in this problem.
Here is my sol CodeChef: Practical coding for everyone

guys help me to find error .Here is my sol CodeChef: Practical coding for everyone

@visharox try testcase for n = 1

I think casting float was the problem? try with double and don’t cast this time to double

I used double and it worked. Why was using float a problem in this case?

because of precision. double offers more precision in the sense say if log(2) to base 2 would be 0.999 in float casting which would be 0 if casted back to int whereas in double it would be rounded off to 1.000

run this and see the pattern

#include <iostream>
using namespace std;

int main() {
    for(int i=1;i<256;i++) {
        int x = i^(i+1);
        cout << i << " " << i+1 << " " << x << endl;
    }
    return 0;
}
1 Like

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.

Positive integers are greater than 0.