Monday, 1 October 2012

Calculating the lower and upper bounds of the bitwise XOR of two bounded variables

Again, the same sort of deal as before. This time with the eXclusive OR (XOR). So the goal is to calculate \begin{equation} \min _{x \in [a, b], y \in [c, d]} x \oplus y \end{equation} And \begin{equation} \max _{x \in [a, b], y \in [c, d]} x \oplus y \end{equation} See how I didn't abuse the notation so badly for once?

Anyway, let's get to it. I'll be honest here, I couldn't solve this one. So no clever bithacks this time. Disappointing, I know. But I still have something relevant to write, so first I'll reproduce Warren's solution from Hacker's Delight and then there will be something relevant.
unsigned minXOR(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;
      } 
      else if (a & ~c & m) {
         temp = (c | m) & -m;
         if (temp <= d) c = temp;
      }
      m = m >> 1;
   }
   return a ^ c;
}

unsigned maxXOR(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;
         temp = (d - m) | (m - 1); 
         if (temp >= c) d = temp;
      }
      m = m >> 1;
   }
   return b ^ d;
}

This time, there is no break. That's because after handling one bit, there may still be more opportunities to decrease (or increase) the value even further. Worse, these opportunities are not necessarily the same as they were before the upper bits were handled. Handling a bit can create more opportunities and at the same time changes the bound such that further changes may not be allowed at all. That's why there is no clever bithack - you have to iterate in some way. Of course you can still skip to a relevant bit in one go, but it's still a loop.

So the "something relevant" I promised is not about how to do it better. Instead, it's about how to extend it to signed values. Warren notes that this can't be done using algebraic equivalences, but that doesn't mean it can't be done.

What has to change to make a signed minXOR? Firstly, the comparison of the potential new lower bound to the corresponding upper bound must be signed, otherwise it would even declare the old bound to be invalid if it crosses zero. And secondly, the signbit needs special treatment, treating it the same as other bits would make the bound go the wrong way (eg setting it as in minXOR doesn't increase a bound, it decreases it, and obviously you can't decrease the lower bound). The same argument about the signbit holds for the other operators, but the functions that preprocess their inputs so they become signed (see Hacker's Delight, Table 4-1) already make sure that that situation never occurs.
int32_t minXORs_internal(int32_t a, int32_t b, int32_t c, int32_t d)
{
    int32_t temp;
    int32_t m = 0x40000000;
    while (m != 0)
    {
        if (~a & c & m)
        {
            temp = (a | m) & -m;
            if (temp <= b) a = temp;
        }
        else if (a & ~c & m)
        {
            temp = (c | m) & -m;
            if (temp <= d) c = temp;
        }
        m = m >> 1;
    }
    return a ^ c;
}

int32_t minXORs(int32_t a, int32_t b, int32_t c, int32_t d)
{
    int32_t r1;
    if (a < 0 && b < 0 && c < 0 && d >= 0) r1 = minXORs_internal(a, b, 0, d);
    else if (a < 0 && b >= 0 && c < 0 && d < 0) r1 = minXORs_internal(0, b, c, d);
    else if (a < 0 && b >= 0 && c < 0 && d >= 0) r1 = 
        min(minXORs_internal(0, b, c, d),
            minXORs_internal(a, b, 0, d));
    else r1 = minXORs_internal(a, b, c, d);

    return r1;
}

What's going on there is that if both lower bounds have their sign set, it tries to avoid cancelling the sign out with the other bound. Having the sign set is obviously always lower than having the sign not set. In the third case, there are two ways to avoid cancelling the sign, which must both be checked to see which way gives the lowest result. For all other cases, the sign is either forced to cancel, or just not set in the first place, so it's all handled by minXORs_internal.

The code for maxXORs is very similar, except of course it doesn't try to avoid cancelling signs, it tried to make them cancel.

Next post, something simpler and more general, so probably more usefull.