bit-manipulation - 计算在 2 的补码中表示整数所需的位数

Question

我必须编写一个函数来计算以 2 的补码形式表示 int 所需的位数。要求：

1. can only use: ! ~ & ^ | + << >>
2. no loops and conditional statement
3. at most, 90 operators are used

目前，我在想这样的事情：

int howManyBits(int x) {
   int mostdigit1 = !!(0x80000000 & x);
   int mostdigit2 = mostdigit1 | !!(0x40000000 & x);
   int mostdigit3 = mostdigit2 | !!(0x20000000 & x);
   //and so one until it reach the least significant digit
   return mostdigit1+mostdigit2+...+mostdigit32+1;
}

但是，这个算法不起作用。它也超过了 90 个操作员的限制。有什么建议，我该如何修复和改进这个算法？

Answer 1

对于 2 的补码整数，问题是负数。负数由最高有效位指示：如果已设置，则该数为负数。2 的补码整数 n 的负数定义为 -(n 的 1 的补码)+1。
因此，我将首先测试负号。如果已设置，则所需的位数只是可用于表示整数的位数，例如 32 位。如果没有，您可以简单地计算所需的位数，方法是将 n 重复右移一位，直到结果为零。例如，如果 n 为 +1，例如 000…001，则必须将其右移一次以使结果为零，例如 1 次。因此，您需要 1 位来表示它。