Given that inverse of XOR is a XOR.
Considering only non-negative integers.
Given 3 integers, a, low and high. We want to find all integers, b, such that:
low <= a^b <= high
Let low=2, high=6, a=1, b is variable.
2 <= 1^b <= 6
Since XOR is inverse of XOR, doing 1^ on each side inequality:
1^2 <= 1^1^b <= 1^6
which simplifies to
3 <= b <= 7
This is incorrect.
b for which 2 <= 1^b <= 6 is 3 but minimum value is 2.1^6 = 7 which does not fall in range of 2 to 6What am I doing wrong?
You are wrong in assuming that XOR is monotonic, and that these two equations below are equal:
2 <= 1^b <= 6 ............... 1^2 <= 1^1^b <= 1^6
This propery is not true at all, by xoring different numbers you might change the order. XOR 1 means simply that you toggle bit 1, so 2 will become 3, but 3 will become 2.