The only difference with the previous post, is that this time, we're interested in the upper bound instead of the lower bound. In other words, evaluate

\begin{equation} \max _{x \in [a, b], y \in [c, d]} x | y \end{equation} The algorithm given by Warren in Hackers Delight is

unsigned maxOR(unsigned a, unsigned b, unsigned c, unsigned d) { unsigned m, temp; m = 0x80000000; while (m != 0) { if (b & d & m) { temp = (b - m) | (m - 1); if (temp >= a) {b = temp; break;} temp = (d - m) | (m - 1); if (temp >= c) {d = temp; break;} } m = m >> 1; } return b | d; }And it's really the same sort of idea as the algorithm to calculate the minimum, except this time we're looking for a place where both

`b`

and `d`

are one, so we can try to reset that bit and set all the bits to the right of it.Warren notes that

`m`

can start at `0x80000000 >> nlz(b & d)`

, and once again the same principle holds: it's enough to *only*look at those bits which are one in

`b & d`

, and they can be visited from high to low with `bsr`

static uint maxOR(uint a, uint b, uint c, uint d) { while (bits != 0) { uint m = 1u << bsr(bits); uint temp; temp = (b - m) | (m - 1); if (temp >= a) { b = temp; break; } temp = (d - m) | (m - 1); if (temp >= c) { d = temp; break; } bits ^= m; } return b | d; }And also, again, we can use that the bit we're looking for in

`b`

must be at or to the right of the leftmost bit in `a ^ b`

(`c ^ d`

for `d`

), and that the selected bit doesn't actually have to be changed.
static uint maxOR(uint a, uint b, uint c, uint d) { uint resettableb = (a ^ b) == 0 ? 0 : 0xFFFFFFFF >> nlz(a ^ b); uint resettabled = (c ^ d) == 0 ? 0 : 0xFFFFFFFF >> nlz(c ^ d); uint candidatebits = b & d & (resettableb | resettabled); uint target = candidatebits == 0 ? 0 : 1u << bsr(candidatebits); uint targetb = target & resettableb; uint targetd = target & resettabled & ~resettableb; uint newb = b | (targetb == 0 ? 0 : targetb - 1); uint newd = d | (targetd == 0 ? 0 : targetd - 1); return newb | newd; }Most of the code should be obvious after a moments thought, but something interesting and non-symmetric happens for

`targetd`

. There, I had to make sure that a change is not made to *both*bounds (that would invalidate the whole idea of "being able to make the change without affecting that bit in the result"). In

`minOR`

that happened automatically because it looked at positions where the bits were different, so both `target`

s couldn't both be non-zero. Here, one of the bounds has to be explicitly prioritized before the other.Next post, maybe the same sort of thing but for bitwise AND. Then again, maybe not. I'll see what I can come up with.

edit: bitwise AND it is.

## No comments:

## Post a Comment