It's the same idea as before, but with bitwise AND instead of OR. That leads to some interesting symmetries. First, the definitions. The lower bound will be \begin{equation} \min _{x \in [a, b], y \in [c, d]} x \& y \end{equation} And the upper bound will be \begin{equation} \max _{x \in [a, b], y \in [c, d]} x \& y \end{equation} The algorithms given by Warren are

unsigned minAND(unsigned a, unsigned b, unsigned c, unsigned d) { unsigned m, temp; m = 0x80000000; while (m != 0) { if (~a & ~c & m) { temp = (a | m) & -m; if (temp <= b) {a = temp; break;} temp = (c | m) & -m; if (temp <= d) {c = temp; break;} } m = m >> 1; } return a & c; }

unsigned maxAND(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;} } else if (~b & d & m) { temp = (d & ~m) | (m - 1); if (temp >= c) {d = temp; break;} } m = m >> 1; } return b & d; }Obviously, the follow the same basic idea. Try to set a bit so you can reset the bits to the right of it in the lower bound, or try to reset a bit so you can set the bits to the right of it in the upper bound. The same reasoning about starting at

`0x80000000 >> nlz(~a & ~c)`

or `0x80000000 >> nlz(b ^ d)`

applies, and the same reasoning about "bits at and to the right of `a ^ b`

" applies as well. I'll skip the "sparse loops" this time, they're nice enough but mainly instructive, and repeating the same idea twice doesn't make it twice as instructive. So straight to the loopless algorithms:
static uint minAND(uint a, uint b, uint c, uint d) { uint settablea = (a ^ b) == 0 ? 0 : 0xFFFFFFFF >> nlz(a ^ b); uint settablec = (c ^ d) == 0 ? 0 : 0xFFFFFFFF >> nlz(c ^ d); uint settable = ~a & ~c & (settablea | settablec); uint target = settable == 0 ? 0 : 1u << bsr(settable); uint targeta = target & settablea; uint targetc = target & settablec & ~settablea; uint newa = a & (targeta == 0 ? 0xFFFFFFFF : 0-targeta); uint newc = c & (targetc == 0 ? 0xFFFFFFFF : 0-targetc); return newa & newc; }

static uint maxAND(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 candidatebitsb = b & ~d & resettableb; uint candidatebitsd = ~b & d & resettabled; uint candidatebits = candidatebitsb | candidatebitsd; uint target = candidatebits == 0 ? 0 : 1u << bsr(candidatebits); uint targetb = target & b; uint targetd = target & d & ~b; uint newb = b | (targetb == 0 ? 0 : targetb - 1); uint newd = d | (targetd == 0 ? 0 : targetd - 1); return newb & newd;Symmetry everywhere. But not really anything to new to explain.

Next post, something new to explain.

## No comments:

## Post a Comment