获取数字的第二个最高有效位

Question

你是一个 C 程序员，给定一个整数 i > 1。你能写一个 msb2 函数 returns 它的第二个最重要的位吗，换句话说：给定一个数字，最左边的 1 位右边的位是多少？即在 1011111 中为 0，在 1100000 中为 1。

不允许：

任何循环（例如分别检查 64 位中的每一位）
浮动算术

允许的是：

所有 C 整数运算符

msb2是否有常数时间（位数为常数，假设所有C整数运算符都采用常数时间，并假设位数不是常数）函数？

我的一个想法：给定i，我们知道i & (i >> 1) >= (1<<((int)log2(i)-1)) <=> msb2(i)=1，但是，log2(i) 不容易计算。也许这仍然可以以某种方式使用？

Answer 1

我相信技术上符合标准：编写 63 if 语句（假设您的整数大小为 64 位），每个可能的解决方案一个。是的，这基本上模仿了循环的作用，但它仍然是恒定时间（相应的循环实际上是这样，但有点难以争论）。

Answer 2

朴素的 log(nbits) 东西：（没有循环！）

#include <stdio.h>

int main(int argc, char **argv)
{
unsigned long org , val;

sscanf(argv[1] , "%lx", &org);

val = org ;

if (val >= (2<<16)) val >>= 16;
if (val >= (2<<8)) val >>= 8;
if (val >= (2<<4)) val >>= 4;
if (val >= (2<<2)) val >>= 2;
if (val >= (2<<1)) val >>= 1;
if (val <= 2) val <<= 1; // This is needed for org = 1 ;-)

printf("%lx -> %lx %c\n"
    , org, val, val&1 ? '+' : '-');

return 0;
}

Answer 3

clz 如果它存在的话，这就变得微不足道了。如果不是，您可以按如下方式计算它的恒定时间。来自这个线程：

http://community.arm.com/thread/6400

static __INLINE uint32_t __CLZ(uint32_t x) {  
    extern uint8_t const log2Lkup[256];  

    if (x >= 0x00010000U) {  
        if (x >= 0x01000000U) {  
            return 8U - log2Lkup[x >> 24];  
        }  
        else {  
            return 16U - log2Lkup[x >> 16];  
        }  
    }  
    else {  
        if (x >= 0x00000100U) {  
            return 24U - log2Lkup[x >> 8];  
        }  
        else {  
            return 32U - log2Lkup[x];  
        }  
    }  
}

该函数需要 .c 文件中定义的 log2（二进制对数）查找 table：

uint8_t const log2Lkup[256] = {  
  0U, 1U, 2U, 2U, 3U, 3U, 3U, 3U, 4U, 4U, 4U, 4U, 4U, 4U, 4U, 4U,  
  5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U, 5U,  
  6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U,  
  6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U, 6U,  
  7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U,  
  7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U,  
  7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U,  
  7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U, 7U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,  
  8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U  
};

我保留了网站上的代码作为示例，因为修改 table 可以使这更容易。

为了解决您的问题，请使用 (32 - clz(x)) - 1 并特别处理 x 为 1 或 0 的情况，因为它未定义。注意：对于 64 位值，只需添加一些查找...

int wantedValue(int x)
{
    if(x <= 1) return -1;

    return (int)(32 - __CLZ(x)) - 1;
}

Answer 4

如果你能得到最左边的1位（见msb64()），剩下的就简单了：

#include <stdio.h>
#include <inttypes.h>

uint64_t msb64(uint64_t x);

int main(int argc, char **argv)
{
    uint64_t x, msb;

    if (argv[1] && sscanf (argv[1], "%lu", &x) == 1) {
        msb = msb64(x);
        printf ("msb2(%lu) = %d\n", x, x & (msb >> 1) ? 1 : 0);
    }
    return 0;
}

uint64_t msb64(uint64_t x)
{
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    x |= (x >> 32);
    return x & ~(x >> 1);
}

$ ./a.out 11
msb2(11) = 0
$ ./a.out 15
msb2(15) = 1

Answer 5

您可以简单地使用

x > (x ^ (x >> 1))

如果 x 以 10 开头，值 (x ^ (x >> 1)) 将以 11 开头，如果 x 以 11。因此，比较给出了所需要的。

获取数字的第二个最高有效位

Get second most significant bit of a number

c

binary

bit-manipulation