任何人都可以解释这个按位函数来计算 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 位表示.假设右移是算术运算。

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

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

也就是说，如果没有评论，我无法破译这段代码在获取符号位值的部分之外做了什么。我用铅笔和纸完成了它，样本 int 的值为 5 - 代码有效，但我不明白为什么。

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

Answer 1

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

如果 x 为正，则 x 保持原样；如果为负，则取补码。这样可以让计算搜索最重要的一个，不管正负

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

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

x = sign ? ~x : x;

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

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

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

下面的连接操作是在原始数字的一个逐渐变小的部分中查找是在高 8 位或低 8 位中选择的 16 位中最重要的一个，然后是高 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 运算符的必要性。

终于把碎片加在一起了。

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

Can anyone explain this bitwise function to compute log(n)

c

logic

bitwise-operators