Bithacking comparison (less) operator

Question

I am aware that most arithmetical operations can be done only using bitwise operators (Add two integers using only bitwise operators?, Multiplication of two integers using bitwise operators, etc ...).

I am also aware, that if you have the less operator you can deduce the other operators from it (Sorting only using the less-than operator compared to a trivalue compare function)

So ... I am simply curios if there is a way of implementing the less operator using only bitwise operations.

Like:

bool less(int a, int b) { ??? }

And to make it more complicated:

template<typename T> bool less(T a, T b) { ??? }

where T certainly is an integral, numerical type (8 ... 64 bit)

Answer 1

It can certainly be done. Assuming two's complement:

bool less(int a, int b)
{
  const unsigned int bits = sizeof(int) * CHAR_BIT;
  const unsigned int sign_bit = 1u << (bits - 1);
  unsigned int lhs = a;
  unsigned int rhs = b;
  bool negative = (lhs & sign_bit);
  if (negative && !(rhs & sign_bit))
    return negative;
  for (unsigned int bit == 1u << (bits - 2); bit != 0u; bit >>= 1) {
    if ((lhs & bit) != (rhs & bit)) {
      return !(lhs & bit);
    }
  }
}

The template version could work the same, with the help of an appropriate make_unsigned<T> trait.