XOR programming puzzle advice

Question

Given a long int x, count the number of values of a that satisfy the following conditions:

a XOR x > x
0 < a < x

where a and x are long integers and XOR is the bitwise XOR operator

How would you go about completing this problem?

I should also mentioned that the input x can be as large as 10^10

I have managed to get a brute force solution by iterating over 0 to x checking the conditions and incrementing a count value.. however this is not an optimal solution...

This is the brute force that I tried. It works but is extremely slow for large values of x.

 for(int i =0; i < x; i++)
 {
      if((0 < i && i < x) && (i ^ x) > x)
          count++;    
 }

Answer 1

One way to look at this is to consider each bit in x.

• If it's 1, then flipping it will yield a smaller number.
• If it's 0, then flipping it will yield a larger number, and we should count it - and also all the combinations of bits to the right. That conveniently adds up to the mask value.

long f(long const x)
{
    // only positive x can have non-zero result
    if (x <= 0) return 0;

    long count = 0;

    // Iterate from LSB to MSB
    for (long mask = 1;  mask < x;  mask <<= 1)
        count += x & mask
            ? 0
            : mask;

    return count;
}

We might suspect a pattern here - it looks like we're just copying x and flipping its bits.

Let's confirm, using a minimal test program:

#include <cstdlib>
#include <iostream>

int main(int, char **argv)
{
    while (*++argv)
        std::cout << *argv << " -> " << f(std::atol(*argv)) << std::endl;
}

0 -> 0
1 -> 0
2 -> 1
3 -> 0
4 -> 3
5 -> 2
6 -> 1
7 -> 0
8 -> 7
9 -> 6
10 -> 5
11 -> 4
12 -> 3
13 -> 2
14 -> 1
15 -> 0

So all we have to do is 'smear' the value so that all the zero bits after the most-significant 1 are set, then xor with that:

long f(long const x)
{
    if (x <= 0) return 0;
    long mask = x;
    while (mask & (mask+1))
        mask |= mask+1;
    return mask ^ x;
}

This is much faster, and still O(log n).

Answer 2

long long NumberOfA(long long x)
{
    long long t = x <<1;
    while(t^(t&-t)) t ^= (t&-t);
    return t-++x;
}


long long x = 10000000000;
printf("%lld ==> %lld\n", 10LL, NumberOfA(10LL) ); 
printf("%lld ==> %lld\n", x, NumberOfA(x) ); 

Output

10 ==> 5
10000000000 ==> 7179869183

Link to IDEOne Code

---

Trying to explain the logic (using example 10, or 1010b)

• Shift x to the left 1. (Value 20 or 10100b)
• Turn off all low bits, leaving just the high bit (Value 16 or 10000b)
• Subtract x+1 (16 - 11 == 5)

---

Attempting to explain
(although its not easy)

Your rule is that a ^ x must be bigger than x, but that you cannot add extra bits to a or x.
(If you start with a 4-bit value, you can only use 4-bits)

The biggest possible value for a number in N-bits is 2^n -1.
(eg. 4-bit number, 2^4-1 == 15)
Lets call this number B.

Between your value x and B (inclusive), there are B-x possible values.
(back to my example, 10. Between 15 and 10, there are 5 possible values: 11, 12, 13, 14, 15)

In my code, t is x << 1, then with all the low bits turned off.
(10 << 1 is 20; turn off all the low bits to get 16)

Then 16 - 1 is B, and B - x is your answer:
(t - 1 - x, is the same as t - ++x, is the answer)