在 C 中仅使用按位运算符计算 log 的下限？(x)

Question

对于家庭作业，使用 C，我应该制作一个程序，该程序仅使用运算符来查找大于 0 的数字的对数基数 2 ! ~ & ^ | + << >>。我知道我应该向右移动多次，但我不知道如何在没有任何循环或ifs 的情况下跟踪次数。我已经被这个问题困住了好几天，所以任何帮助表示赞赏。

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));
}

Answer 2

这得到了一个数字的 logbase2 的下限。

int ilog2(int x) {

    int i, j, k, l, m;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);

    // i = 0x55555555 
    i = 0x55 | (0x55 << 8); 
    i = i | (i << 16);

    // j = 0x33333333 
    j = 0x33 | (0x33 << 8);
    j = j | (j << 16);

    // k = 0x0f0f0f0f 
    k = 0x0f | (0x0f << 8);
    k = k | (k << 16);

    // l = 0x00ff00ff 
    l = 0xff | (0xff << 16);

    // m = 0x0000ffff 
    m = 0xff | (0xff << 8);

    x = (x & i) + ((x >> 1) & i);
    x = (x & j) + ((x >> 2) & j);
    x = (x & k) + ((x >> 4) & k);
    x = (x & l) + ((x >> 8) & l);
    x = (x & m) + ((x >> 16) & m);
    x = x + ~0;
    return x; 
}