仅使用 C 中的按位运算符计算 log2(x) 的底数

Question

对于家庭作业，我应该使用 C 编写一个程序，仅使用运算符 ! ~ & ^ | + << >> 来查找大于 0 的数字的对数基数 2| .我知道我应该向右移动很多次，但我不知道如何在没有任何循环或 if 的情况下跟踪次数。秒。我已经在这个问题上停留了好几天，所以非常感谢您的帮助。

int ilog2(int x) {
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
}

这就是我目前所拥有的。我将最高有效位传递到最后。

Answer 1

假设一个 32 位 unsigned int :

unsigned int ulog2 (unsigned int u)
{
    unsigned int s, t;

    t = (u > 0xffff) << 4; u >>= t;
    s = (u > 0xff  ) << 3; u >>= s, t |= s;
    s = (u > 0xf   ) << 2; u >>= s, t |= s;
    s = (u > 0x3   ) << 1; u >>= s, t |= s;

    return (t | (u >> 1));
}

---

因为我假设 > ，我想我会找到摆脱它的方法。

(u > 0xffff)相当于:((u >> 16) != 0) .如果减法借位:
((u >> 16) - 1)将设置 msb，iff (u <= 0xffff) .替换 -1与 +(~0) (允许)。

所以条件:(u > 0xffff)替换为:(~((u >> 16) + ~0U)) >> 31

---

unsigned int ulog2 (unsigned int u)
{
    unsigned int r = 0, t;

    t = ((~((u >> 16) + ~0U)) >> 27) & 0x10;
    r |= t, u >>= t;
    t = ((~((u >>  8) + ~0U)) >> 28) &  0x8;
    r |= t, u >>= t;
    t = ((~((u >>  4) + ~0U)) >> 29) &  0x4;
    r |= t, u >>= t;
    t = ((~((u >>  2) + ~0U)) >> 30) &  0x2;
    r |= t, u >>= t;

    return (r | (u >> 1));
}