Search code examples
xor

Inequality with XOR


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?


Solution

  • 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.