Bithacking比较(less)运算符

Question

我知道大多数算术运算只能使用按位运算符(Add two integers using only bitwise operators?、Multiplication of two integers using bitwise operators等)来完成。

我还知道，如果你有较少的运算符，你可以从它推导出其他运算符(Sorting only using the less-than operator compared to a trivalue compare function)

所以..。如果有一种方法可以只使用按位运算来实现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>特征的帮助下，模板版本也可以工作。