XOR puzzle programming

Question

Given the long int x, count the number of values ​​of a satisfying 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 could you solve this problem?

I should also mention that input x can reach 10 ^ 10

I managed to get a brute force solution, iterating from 0 to x, checking conditions and increasing the count value. However, this is not an optimal solution ...

This is the brute force I tried. It works, but very small for large x values.

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

Answer 1

 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 logic (using example 10 or 1010b )

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

---

Attempt to explain
(although its not easy)

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

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

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

In my code t there is x << 1 , then when turning off all the least significant bits.
( 10 << 1 - 20 ; turn off all the low bits to get 16 )

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

Answer 2

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

• If it is 1, then turning it over will give you a lower number.
• If it is 0, then rebooking it will give a larger number, and we must consider it - as well as all combinations of bits to the right. This conveniently adds a 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.

Confirm using the minimum 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 need to do is “grease” the value so that all the zero bits after the most significant 1 are set, then xor with this:

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

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