Search code examples
algorithmlanguage-agnosticbit-manipulation

Bitwise Interval Arithmetic


I've recently read an interesting thread on the D newsgroup, which basically asks,

Given two (signed) integers a ∈ [amin, amax], b ∈ [bmin, bmax], what is the tightest interval of a | b?

I'm think if interval arithmetics can be applied on general bitwise operators (assuming infinite bits). The bitwise-NOT and shifts are trivial since they just corresponds to -1 − x and 2n x. But bitwise-AND/OR are a lot trickier, due to the mix of bitwise and arithmetic properties.

Is there a polynomial-time algorithm to compute the intervals of bitwise-AND/OR?


Note:

  • Assume all bitwise operations run in linear time (of number of bits), and test/set a bit is constant time.
  • The brute-force algorithm runs in exponential time.
  • Because ~(a | b) = ~a & ~b, solving the bitwise-AND and -NOT problem implies bitwise-OR is done.
  • Although the content of that thread suggests min{a | b} = max(amin, bmin), it is not the tightest bound. Just consider [2, 3] | [8, 9] = [10, 11].)
  • Actually working on unsigned arithmetic is enough, as we can split a signed interval into negative and nonnegative subsets, and using de Morgan's laws and commutativity only the bitwise-AND, -OR and -AND-NOT cases on nonnegative intervals need to be solved.

Solution

  • For an interval [amin, amax] of non-negative integers we can compute a bitwise minimum a0, where bits are independently set to 0 whenever that is possible within the interval. Similarly, we can compute a bitwise maximum a1 where bits are set to 1 as much as possible in the interval. For [bmin, bmax] we do the same and get b0 and b1. Then the result interval is [a0 | b0, a1 | b1].

    It is easy to check for a bit which values it can take for an a from [amin, amax]. For bit n, if all bits m with m >= n agree in amin and amax 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.

    Edit: Unfortunately this is wrong: Consider the case where [amin, amax] = [bmin, bmax] = [1,2]. Then a | b can be either 1, 2 or 3, but the bitwise minimum is 0.