任何人都可以解释这个按位函数来计算 log(n)

Question

int howManyBits(int x) {
    int concatenate;
    int bias;
    int sign = x >> 31;  //get the sign
    x = (sign & (~x)) | (~sign & x); 
    concatenate = (!!(x >> 16)) << 4;
    concatenate |= (!!(x >> (concatenate + 8))) << 3;
    concatenate |= (!!(x >> (concatenate + 4))) << 2;
    concatenate |= (!!(x >> (concatenate + 2))) << 1;
    concatenate |= x >> (concatenate + 1);
    bias = !(x ^ 0);
    return concatenate + 2 + (~bias + 1);

}

这段代码是作为一种方法来计算用 2 的补码表示整数 n 所需的最少位数，假设 int 数据类型是用 32 位表示。假设右移是算术运算。

我理解的基本方法是取n的log base 2，四舍五入，然后加1位来占符号位。

我也明白，左移相当于乘以2，右移相当于除以2。

话虽这么说，但如果没有注释，我无法破译这段代码在获取符号位值的部分之外做了什么。我用铅笔和纸用值为 5 的示例 int 完成了它 - 代码有效，但我不明白为什么。

有人可以直观地分析代码的作用吗？

Answer 1

此代码可以使用一些注释。

如果 x 为正，则 x 保持原样；如果为负，则取 1 的补码。这允许计算搜索最显着的一个，而不管正数或负数

x = (sign & (~x)) | (~sign & x);

我认为下面的内容会更清楚:

x = sign ? ~x : x;

接下来是通过二分法搜索最高 1 位。首先搜索单词的上半部分。

concatenate = (!!(x >> 16)) << 4;

如果上半部分有 1，则结果为 16。16 稍后用作答案的一部分，同时也用于确定下一步要搜索的位置。由于它在随后的轮类中使用，因此将导致以下测试要么在电路板的上半部分完成，要么在下半部分完成。

以下连接操作是在原始数字的逐渐变小的部分中搜索，查找所选择的 16 位中的高 8 位或低 8 位中的最高位，然后是高 4 位或低位选择的 8 位中的 4 位，依此类推。

concatenate |= (!!(x >> (concatenate + 8))) << 3; // Check which 8 bits
concatenate |= (!!(x >> (concatenate + 4))) << 2; // Check which 4 bits
concatenate |= (!!(x >> (concatenate + 2))) << 1; // Check which 2 bits
concatenate |= x >> (concatenate + 1);            // Check which 1 bit

偏差只是检查数字是否为 0。仅当 x 为 0 时才为 1。我不明白 XOR 运算符的必要性。

最后将这些片段加在一起。