c++ - Bithacking 比较(较少)运算符

Question

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

我也知道，如果你有 less 运算符，你可以从中推断出其他运算符 (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> 的帮助下，模板版本可以工作相同特质。