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.