[Solved] “Little girl and maximum XOR”

by


If you read about __builtin_clzll in http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html

— Built-in Function: int __builtin_clzll (unsigned long long x)

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

From https://cs.stackexchange.com/a/29510,

The maximum possible XOR of any two integers from an interval [l, r] can be determined from l ⊕ r, assuming l, r to be integers. This value is equal to pow(2, p) − 1, where p is the smallest value such that pow(2, p) is larger than l ⊕ r.

Now, relating with the code,

val = 64 - __builtin_clzll(l ^ r);    // p

(1LL << val) - 1;    // pow(2, p) - 1

1

solved “Little girl and maximum XOR”