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

Given two signed integers a ∈ [a_min, a_max], b ∈ [b_min, b_max], 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 2ⁿ 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(a_min, b_min), it is not the tightest bound. Just consider [2, 3] | [8, 9] = [10, 11].)