Bitwise Interval Arithmetic
- by KennyTM
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 and a ^ b = (a | b) & ~(a & b), solving the bitwise-AND and -NOT problem implies bitwise-OR and -XOR are 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].)
