5

我试图找到一个数字的二进制基数，比如将数字四舍五入到它下面的最大整数的 floor 函数，我想将数字四舍五入到它下面的第一个二进制基数。

例如：

for 1000 it should be 512
for 10 it should be 8
for 208 it should be 128

这是我尝试过的。我觉得日志功能会消耗更多资源，那么有没有更快的方法呢？

#include<stdio.h>
int main()  {
    unsigned long long int num;
    unsigned long long int mask;
    scanf("%llu", &num);
    mask = 0x80000000;
    while(mask >>= 1)   {
        if (mask & num)
            break;
    }
    printf("%llu\n", mask);
    return 0;
}

谢谢：）

4

11 回答 11

5 
int topBit(int n) {
    while (true){
        m = n & (n-1);
        if (m == 0) return n;
        n = m;
    } 
}

n & (n-1)清除最底部的设置位。这样做直到你达到零，然后你知道之前的值只设置了一个位（输入中设置的最高位）。

于 2013-05-30T03:03:41.357 回答
2

用二进制表示数字，然后查找最高有效位（最高的非零位）。天真地你可以通过一次右移一位直到它为零来做到这一点 - 那是“一个太多”。这基本上就是你尝试的方法。更快一点将是二进制搜索。对于 32 位整数，右移 16；如果仍然 > 0，则右移 8 位等。我相信您可以从这里弄清楚。

代码示例：

typedef unsigned long long int ulli;
ulli floor2(ulli num){
  int msb = 8*sizeof(num)/2;
  ulli temp = ((ulli)1)<<msb;
  while(msb>1){
    msb/=2; // using divide for clarity
    if(temp>num) temp>>=msb; else temp<<=msb;
  }
  if (temp>num) temp/=2;
  return temp;
}

我针对该算法topBit以及该builtIn方法运行了该算法的一些基准测试。具有 10M 次迭代的循环生成一个“长”随机数，在我的系统上需要 362 毫秒（没有编译器优化）。如果循环包括其中一种计算方法，则时间增加如下：

=============  total    net
builtin:         407     45
binary search:   579    215
topBit:         2295   1933

内置的方法绝对是最快的，而且有很大的差距——这并不奇怪！对于 64 位数字，topBit 平均需要 32 个循环（设置了一半的位，所以跳过），二进制只需要 5 个循环，因此您预计速度差异约为 6 倍；这大致就是您所看到的。当我定义ulli为unsigned short（16位）时，时间差约为2倍。

于 2013-05-30T02:39:50.417 回答
2

如果您使用 GCC 进行编译，您可以使用GCC builtins来执行此操作。内置函数__builtin_clzll计算 unsigned long long 中前导零的数量。您可以使用它来计算最高有效位的位置，然后多次左移 1 以获得您的答案：

#include <limits.h>

然后使用：

unsigned long long result = 
  num ? 1LLU << (sizeof(unsigned long long)*CHAR_BIT - __builtin_clzll(num) - 1) : 0;

printf("%llu\n", result);
于 2013-05-30T04:49:05.810 回答
2

这个经典文档有很多方法可以找到整数的底数（对数基数 2）。找到日志后，你想要的数字当然是 1 << log.

最有趣的建议是这个

// Find the integer log base 2 of an integer with an 64-bit IEEE float 
int v; // 32-bit integer to find the log base 2 of
int r; // result of log_2(v) goes here
union { unsigned int u[2]; double d; } t; // temp

t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;

上面的代码通过将整数存储在尾数中同时将指数设置为 252 来加载带有 32 位整数（没有填充位）的 64 位（IEEE-754 浮点）双精度数。从这个新生成的双精度数中，减去 252（表示为双精度），将结果指数设置为输入值 v 的以 2 为底的对数。剩下的就是将指数位移动到适当的位置（向右 20 位）并减去偏差 0x3FF（这是十进制的 1023）。这种技术只需要 5 次操作，但许多 CPU 处理双精度数的速度很慢，而且必须适应架构的字节序。

所以你想要的最终结果将是1 << r. 请注意，现在对双精度数的操作比撰写本文时要快得多。这段代码最好的一点是它不包含任何分支，所以流水线会很好。你绝对应该试一试。我现在没有时间尝试基准测试，但这会很有趣。

我不能保证这段代码符合 C 标准。

于 2013-05-30T13:42:25.787 回答
1

我假设如果一个数字已经是 2 或 0 的幂，它应该原封不动地返回。仅限正数。

int floor2(int n)
{
    if ((n & (n-1)) == 0)
        return n;
    while (((n+1) & n) != 0)
    {
        n = n | (n+1);
    }
    return (n + 1) >> 1;
}

这里花哨的位旋转利用了这样一个事实，即用一个位（即 2 的幂）从一个数字中减去 1 设置它下面的所有位，而将一个数字加 1 将设置最底部的零位。

于 2013-05-30T02:42:20.030 回答
1

这是一个与寻找最高位问题密切相关的问题；因为在那之后它只是有点移位：

找到 MSB 在这里有很好的描述：

查找在位数组中设置的最高有效位（最左侧）

然后你做这样的事情：

int foo = 1000;
int bar = ((msb(foo) << 1) - 1) >> 1; 
if ( bar > foo ) bar = bar >> 1;

你有它。

如果您使用的是 intel 架构，则可以在 gcc 中使用 __builtin_clz （计算前导零）来获取 msb；

或者

这是一种在没有 CPU 支持的情况下计算前导零的非常有趣的方法

http://www.hackersdelight.org/hdcodetxt/nlz.c.txt

于 2013-05-30T02:47:10.847 回答
1

简短而甜蜜...
（提问者的示例代码在值 >= 0x80000000LLU 时遇到问题，已在此处修复。）
这只需要在循环中进行 1 次比较，而不是 2 次。

unsigned long long int MSMask(unsigned long long int) {
  if (num == 0) {
    return 0;
    }
  else {
    unsigned long long int mask = 0x8000000000000000LLU;
    while (!(mask & num)) mask >>= 1;
    return mask;
  }
}
于 2013-05-30T03:47:00.557 回答
0

这比您的版本快大约 2 倍：

uint64_t g(uint64_t num) {
    uint64_t r = 1;
    num = num >> 1;
    while(num>r)   {
        r <<= 1;
    }
    return r;
}
于 2013-05-30T02:50:45.513 回答
0 
int test(int num) {
    int res = (num==0?0:1);
    while(num>1) {
        num=num>>1;
        res=res<<1;
    }
    return res;
}

当 num 不大时，比下面快。

于 2013-05-30T03:05:07.233 回答
0

建议的位旋转技巧的最坏情况性能可以/应该通过逐渐将or几个位变为 1 来改善：

 int s=1;
 while ((n+1) & n) {
    n|=n >> s;
    s<<=1;
 }
 return (n+1) >> 1;

当所有最低有效位均为 1 时，此片段退出，仅需要一些 log2(log2(n)) 迭代。

于 2013-05-30T04:19:34.767 回答
0

我知道递归通常不如迭代有效，但我忍不住——我喜欢一个好的递归：

unsigned topBit(unsigned n) {
   unsigned m = n & (n-1);
   return m ? topBit(m) : n;
}

附录：实际时间显示，在使用优化编译时，这比@LaurenceGonsalves 的迭代版本略快。

于 2013-05-30T19:01:45.753 回答