Compare 64-bit integers by segments

Question

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?

This doesn't really answer the question as posed, but solves a very similar problem: 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`) — Aleksi Torhamo, Jun 03 '18 at 05:01
You could convert into the form @AleksiTorhamo describes by masking out alternating sections, meaning just two subtraction operations and four `&` operations. But it still gives `<=`, so you could add an appropriately padded all-fields-1 value. The result isn’t better than what you have but is still fun. =) — Ry-, Jun 03 '18 at 05:05
@AleksiTorhamo Thank you so much! Your answer actually solves my problem because I have the freedom to repack the data in my algo. If you want to post your comment as an answer I'll accept it. — user2961927, Jun 03 '18 at 05:13
You can use the carry-out vector technique [used by Bochs](https://sourceforge.net/p/bochs/code/HEAD/tree/branches/REL_2_6/bochs/cpu/lazy_flags.h#l55). The carry-out vector calculates whether a borrow happened at any particular position. So you can subtract the values, calculate the carry-out vector, and then test bits 9, 22, 38, 52, and 63 (which can be done with a single `&` operation). `if (((~x & y) | (~(x ^ y) & (x-y)) & 0x8010004000400200) { /* underflow */ }` (check my math) — Raymond Chen, Jun 04 '18 at 01:26

score 2 · Accepted Answer · answered Jun 03 '18 at 05:18

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)

score 0 · Answer 2 · answered Jan 09 '20 at 02:48

You can use bit field

#include <iostream>
#include <string.h>
#include <stdint.h>

struct CombInt64 {
        CombInt64(uint64_t x) {
                memcpy(this, &x, sizeof(uint64_t));
        }

        bool operator < (const CombInt64& other) const {
                std::cout << "Debug: self.a: " << a << " other.a: " << other.a << std::endl;
                std::cout << "Debug: self.b: " << b << " other.b: " << other.b << std::endl;
                std::cout << "Debug: self.c: " << c << " other.c: " << other.c << std::endl;
                std::cout << "Debug: self.d: " << d << " other.d: " << other.d << std::endl;
                std::cout << "Debug: self.e: " << e << " other.e: " << other.e << std::endl;

                return a < other.a && b < other.b && c < other.c && d < other.d && e < other.e;
        }
#if __BYTE_ORDER == __LITTLE_ENDIAN
        uint64_t a:10;
        uint64_t b:13;
        uint64_t c:16;
        uint64_t d:14;
        uint64_t e:11;
#elif __BYTE_ORDER == __BIG_ENDIAN
        uint64_t e:11;
        uint64_t d:14;
        uint64_t c:16;
        uint64_t b:13;
        uint64_t a:10;
#endif
};

bool allLess(uint64_t x, uint64_t y) {
        return CombInt64(x) < CombInt64(y);
}

int main(void) {
        std::cout << allLess(123, 45) << std::endl;
}

Output

[root@localhost tmp]# ./a.out
Debug: self.a: 123 other.a: 45
Debug: self.b: 0 other.b: 0
Debug: self.c: 0 other.c: 0
Debug: self.d: 0 other.d: 0
Debug: self.e: 0 other.e: 0
0

not full tested!!!

Compare 64-bit integers by segments

2 Answers2

Output

Linked