c++bit-manipulationswar

Compare 64-bit integers by segments


I have two 64-bit integers x and y. Each of them represents 5 short unsigned integers: the first 10 bits represent the first integer, the next 13 bits represent the 2nd integer, the next 16 bits represent the 3rd integer, the next 14 bits represent the 4th integer, and the rest bits represent the 5th integer.

Let x0, x1, x2, x3, x4 be the 5 short integers that constitute x. Let y0, y1, y2, y3, y4 be the 5 short integers that constitute y. I need to know if x0 < y0 AND x1 < y1 AND x2 < y2 AND x3 < y3 AND x4 < y4.

I assume the simplest solution is to shift:

bool allLess(std::size_t x, std::size_t y)
{
  if(x >= y) return 0;
  int shift[] = {10, 13, 16, 14};
  for(int i = 0; i < 4; ++i)
  {
    x <<= shift[i];
    y <<= shift[i];
    if(x >= y) return 0;
  }
  return 1;
}

I know there are lots of bitwise gymnastics. Any faster solution?


Solution

  • This doesn't really answer the question as posed, but solves a very similar problem: (Which might help if one is in the position to reorganize the actual problem, like the OP)

    If the integers weren't tightly packed (ie. if there was a single zero bit of padding between each "field", and at the MSB end), and you wanted to know <= instead of <, I think you might be able to just subtract the numbers and check if any of the padding bits changed. (ie. (y - x) & PADDING_MASK)