GTXOR - Editorial

#PROBLEM LINK:

Practice
Contest

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.

2 Likes