Оператор сравнения битхаков (меньше)

Question

Мне известно, что большинство арифметических операций могут быть выполнены только с использованием побитовых операторов ( Добавить два целых числа, используя только побитовые операторы?, Умножение двух целых чисел, используя побитовые операторы, и т. Д...).

Я также знаю, что если у вас есть оператор меньше, вы можете вывести из него другие операторы ( сортировка только с использованием оператора меньше чем по сравнению с функцией сравнения трех значений)

Итак... Я просто любопытен, если есть способ реализовать оператор less, используя только побитовые операции.

Подобно:

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

И чтобы сделать это более сложным:

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

где T, безусловно, является целочисленным числовым типом (8 ... 64 бит)

Answer 1

Это, безусловно, можно сделать. Предполагая два дополнения:

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);
    }
  }
}

Версия шаблона может работать так же, с помощью соответствующего make_unsigned<T> черта характера.