# 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 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. 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. 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