`z`

is a bitmask containing the bits that are allowed to be 0, and `o`

is a bitmask containing the bits that are allowed to be 1.The idea behind the algorithms is to do a binary search (the one-sided variant) over the numbers that the masks allow, for the lowest value bigger than or equal to the original lower bound (or smaller than or equal to the original upper bound, for the new upper bound). Just as in the case of propagating bounds through XOR, it may take more than one step, so there aren't many shortcuts. I called them both "reduce" even though

`ReduceMin`

actually increases the value, because their purpose is to reduce the range `[min, max]`

.
static uint ReduceMin(uint min, uint z, uint o) { uint mask = z & o; // note: mask is a subset of r uint r = o; uint m = 0x80000000 >> nlz(mask); while (m != 0) { // reset the bit if it can be freely chosen uint newr = r ^ (m & mask); if (newr >= min) // keep the change if still within bounds r = newr; m >>= 1; } return r; }

static uint ReduceMax(uint max, uint z, uint o) { uint mask = z & o; uint r = ~z; uint m = 0x80000000 >> nlz(mask); while (m != 0) { // set the bit if it can be freely chosen uint newr = r | (m & mask); if (newr <= max) // keep the change if still within bounds r = newr; m >>= 1; } return r; }

There is one shortcut (that I know of): using

`nlz`

on every iteration, thereby skipping iterations where the current bit isn't even changed. With the implementation of `nlz`

I was working with, that wasn't worth it, so whether it's actually a real shortcut or not is up for debate.Occasionally the new lower bound can be higher than the new upper bound, that means the set of values was actually empty. If you were working with clockwise intervals, that changes to "if the new bounds aren't ordered the same way as the old ones" - ie if the interval was proper and the new one isn't or vice versa, the set is empty.

## No comments:

## Post a Comment