Finding the min and max value of bitwise operations (solved)

Hello,

Let's say I have two integers that are bounded by a RangeInclusive each. I want to know what the maximum and minimum the result can be if I apply bitwise operations And, Or or Xor.

See this function:

fn test(op: Op, a: RangeInclusive<i8>, b: RangeInclusive<i8>) -> RangeInclusive<i8> {
    let mut start = i8::MAX;
    let mut end = i8::MIN;
    for x in a {
        for y in b {
            let z = match op {
                Op::And => x & y,
                Op::Or => x | y,
                Op::Xor => x ^ y,
            };
            if z < start {
                start = z;
            }
            if z > end {
                end = z;
            }
        }
    }
    start..=end
}

It works well enough for i8 but if I changed the type to a larger integer, it gets inefficient quickly.

So this approach is bad. I want to find a better way.

My alternative approach for that already got quite far:

However you'll notice that on Run the result is not correct. I stared on my code for some time now and I guess I need another pair of eyes.

I tried to add helpful comment but let me explain the idea again:

As I am interested in the minimum or maximum possible value, so my interest is on the most significant bits of the ranges. Basically I check what these can be and, if at least one range offers both 1 and 0 at this bit, which I want to pick to get either the minimum or maximum value.

Once I did that, I reduce the range in question to the part where the bit has the desired value. For example range a can only be 1 at the highest bit, but range b can be both. If I look for the maximum value for the And operation, I pick 1 for range b.

Right? Almost. The highest bit might be a sign bit. It is for the case of i8. positive numbers have 0 as the sign. So I actually want the And operation to result in false/0.

So when a can be only 1, b needs to be 0.

But what if a can be only 0? That'd mean b can be both 0 and 1 at this bit for the desired result. But a less significant bit can make the difference in which I want to pick. If the next significant bit is always 0 if I pick 1 now for b, I will not get 1 for that following bit for my And operation. But if I pick 0 for the most significant, the next bit can be 1.

This becomes a bit more obvious if b is -1i8..=0i8. That means one value of b can be 0b0000000 (0) and the other 0b11111111 (-1). If the most significant bit of a can only be 0 but the next bit is 1, I want to pick 1 for the most significant bit of b because that means both a and b are 1 in their second most-significant bit, which would result in 0b01... with my And operation. Just what I want if I search the maximum number.

The algorithm does that by working recursively. If the bit n offers multiple solutions for now, it generates results for each of them and then check for the min or max value to return.


Okay, that is how it should work. But it doesn't sadly. I would appreciate if someone could take a look in my algorithm.

Thanks :wave:


EDIT1: I fixed an issue with handling the least significant bit. Result seems better but still not fully correct.
EDIT2: I fixed an issue in the matching function at the bottom regarding Or. Still the result is off by one...
EDIT3: I found the last issue. I tested around with other ranges and now it seems to work. :partying_face:

Since I found the bugs and the algorithm seems to work, I further optimized it for those who are interested in this.

This further reduces the number of iterations greatly. The difference:

If one of these solution is across a full sub range, for example 0bXX100000..=0bXX111111 for the 3rd most significant bit being 1, I don't check further down if it matters which value I take for the 4th most significant bit. As I know every following bit can be both 0 and 1, I just pick one that results in the desired result for the 3rd most significant bit.

I hope that made sense. :sweat_smile:

For comparison, if both a and b are -128..=127, then...

  • ...the brute-force function with double for I quoted in the OP went 65536 times through the inner loop body.
  • ...my function algo on the Playground in the OP was called 1116 times for And/Or and 510 times for Xor.
  • ..my optimized function algo on the Playground in this post was called 30 times.

EDIT: const fn variant

1 Like