#PROBLEM LINK:
Author: Ayush Nagal
#DIFFICULTY:
MEDIUM
#PREREQUISITES:
Bit Manipulation
#PROBLEM:
Given a long integer x, we have to find the number of values of a such that 0<a<x and a⊕x >x.
#EXPLANATION:
Let’s take an example, let the number x be 111010111 . Let’s start traversing the bit string from right to left, i.e., from lsb to msb. We can’t change the first, second or third bits as this would produce a number less than x. When we come to the 4th bit which is 0, we flip it to 1 (using XOR) and then we have 2^n choices to change the bits after that where n is the number of bits after the 4th bit. Then we move on to the next bit which is 1. Similarly, we continue traversing and flip 0 every time we encounter it and calculate the possibilites (2^n) and keep adding them. Consider the following snippet:
while (x > 0) {
if ((x & 1) == 0)
s += pow(2, i);
i++;
x = x >> 1;
}
Where x is the given integer and i is used for number of bits.
#AUTHOR’S SOLUTION:
Author’s solution can be found here.