0

我的需求：

对于任何非负 unsigned long a，

输入 a = 5; 答案应该是 3

输入 a = 12; 答案应该是 4

输入 a = 1; 答案应该是 1

输入 a=0 Ans 应该是 0

即从左边找到最重要的1个位置。

我试过的：

int count = 0;

if( a!=0 )
 do{
   count++;
 }while( a >>= 1 );

问题 由于 while 循环和移位而需要更多时间。

建议的方法 如果我知道这 4 个字节是如何存储在内存中的，（使用 char*）我将取出包含最重要的 1 的字节，因此在最坏的情况下，最多 8 次移位就足以找到答案。

4

2 回答 2

1

不要那样做。如果最高有效字节不包含您要查找的位（即，如果您的数字小于2 ^ (3 * CHAR_BIT)），您的方法将不起作用。你为什么不从另一端开始？

unsigned find_msb(unsigned long long n)
{
    int bits_max = sizeof(n) * CHAR_BIT - 1;
    int i;
    for (i = bits_max; i >= 0; i--) {
        if ((n >> i) & 1) return i + 1;
    }
    return 0;
}
于 2013-02-23T17:13:14.163 回答
1

我认为您担心效率的方式。最坏的情况是 O(n)，坦率地说，它永远不会变得更好。即使在慢速处理器上的嵌入式系统中，也没有真正需要尝试加速 H2CO3 的算法。

让它工作，然后担心效率。

于 2013-02-23T19:50:43.087 回答