Inequality with XOR

Question

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.

1. According to this minimum value of b for which 2 <= 1^b <= 6 is 3 but minimum value is 2.
2. b can take value of 6 but 1^6 = 7 which does not fall in range of 2 to 6

What am I doing wrong?

Answer 1

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.