Bitwise Interval Arithmetic

Answer 1

Argh. Are you sure these have to be signed integers? That just brings up a pile of annoying cases where you have to flip things.

If we limit ourselves to unsigned integers, we can just walk down the bits to find the maximum. Any bit above the highest bit set in max(a_max , b_max) obviously can't be on. Assume without loss of generality that a_max > b_max. Keep all the bits in a_max until we hit the highest bit in b_max. Then keep all the bits of both until we have flexibility on at least one side (i.e. we can choose a number in the range allowed that will flip that bit). If the other side cannot set that bit to 1, set it to 1 and keep going (setting one higher bit always beats setting all lower bits). Otherwise, set your answer to (that bit - 1), which will places 1's in all the rest of the bits and you're done.

Now we do the same sort of thing for the minimum, except we avoid setting bits at every opportunity, but take every opportunity to pair bits if one side must set one.

This is O(n) in the number of bits if we can do math on the integers in O(1) time. Otherwise, it's O(n^2).

Here's how it works on your example of [2,3] | [8,9]

101 -> 1xx works
10 to 11 -> x1x always set ; 11x doesn't fit in a so we're not done
11 can set last bit -> 111
100 -> 1xx must be set
10 to 11 -> x1x must be set ; 11x doesn't fit so we're not done
10 has xx0 as does 100 -> xx0 works -> 110

Edit: adding sign bits doesn't change the order of the algorithm, but it does require more annoying bookkeeping. If you cannot get rid of a sign bit, then you flip min and max strategies (i.e. set vs. don't set bits). If it's optional, the min is when you set it and then try to keep everything else unset; the max is when you unset it and then try to keep everything else set.

Second edit: here's another example; both ranges are [1001,1100]:

Must keep first bit -> 1xxx
Can set 2nd bit -> x1xx
Other _could have but did not need to_ set 2nd bit -> set 2nd bit -1 -> xx11
-> 1111 is max
Must keep first bit -> 1xxx
Neither needs 2nd bit -> x0xx
Neither needs 3rd bit -> xx0x
Both need 4th bit -> xxx1
-> 1001 is min

Answer 2

For an interval [a_min, a_max] of non-negative integers we can compute a bitwise minimum a₀, where bits are independently set to 0 whenever that is possible within the interval. Similarly, we can compute a bitwise maximum a₁ where bits are set to 1 as much as possible in the interval. For [b_min, b_max] we do the same and get b₀ and b₁. Then the result interval is [a₀ | b₀, a₁ | b₁].

It is easy to check for a bit which values it can take for an a from [a_min, a_max]. For bit n, if all bits m with m >= n agree in a_min and a_max then the value is forced, otherwise it can be 0 or 1.

This can be done in O(n).

The signed case is left as an exercise for the reader. The first step is to provide a definition what the bitwise operators mean for negative integers.