寻找二进制基数的最快方法

Question

我将尝试寻找一个数字的二进制基数，类似于向下取整功能，它将数字舍入到其下面最大的整数。我想将数字舍入到比它小的第一个二进制基数。

例如：

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

谢谢 :)

- SureshS

---

接近但不完全是重复的问题：https://dev59.com/DXRB5IYBdhLWcg3wSVcI - Shafik Yaghmour

你可能想看一下Andrei Alexandrescu的《C++三个优化技巧》（http://isocpp.org/blog/2012/12/three-optimization-tips-alexandrescu），他在其中使用了这个问题作为例子。幻灯片：第24页，视频：约30:00。 - Jerry Coffin

看看这个无分支代码，用于查找 ceil(log2(x))：https://dev59.com/UnA75IYBdhLWcg3weZDu#15327567 -- 或许你可以适应它。 - paddy

不完全是一个重复的解决方案，尽管那个解决方案非常好。@bugsbunny：如果你想要一个简单易懂的方法，你可以尝试“向上取最接近2的幂”的算法在这里，然后右移1位。 - phuclv

Answer 1

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

n & (n-1) 可以清除最低位的 1。只需反复执行此操作，直到结果为零，然后即可确定输入值中最高位为 1 的位数。

- Laurence Gonsalves

---

这很好地补充了@markransom的答案。位与和位或！两者都可以。很酷。在小整数上可能更快；我想知道二分查找在哪个大小的整数上胜出... - Floris

我也喜欢它，比我的更短更清晰。 - Mark Ransom

Answer 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次迭代，生成一个“long”随机数，需要362毫秒（没有编译器优化）。如果循环包括其中一种计算方法，则时间增加如下：

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

内置方法绝对是速度最快的，这并不令人惊讶！使用64位数字时，topBit平均需要32个循环（有一半的位被设置了，所以会被跳过），而二进制只需要5个循环，因此您可以预期速度差异约为6倍；这大致就是您看到的。当我将ulli定义为unsigned short（16位）时，时间差异约为2倍。

- Floris

---

msb = sizeof(num) >> 1; 这句话的意思是什么？msb(3524) != sizeof(3524) >> 1; sizeof(3524) == sizeof(2)（在32位平台上为4） - Ahmed Masud

@ahmedmasud 我选择的变量名不太好。temp 最终会成为你要找的数字。如果 int 是 32 位，则 msb 开始为 16，因此 temp=1<<16 是第一个猜测，以此类推。我编辑了答案以澄清问题；感谢你指出来！ - Floris

这个解决方案在num的任何上位比特设置时都会出现问题。int topBit(int n)，Paulpro和其他解决方案更快且完整。顺便说一句，这是一个有趣的练习。 - chux - Reinstate Monica

任何一个好的编译器都会将除以2的操作转换为移位操作。编码时最好注重清晰易懂，特别是那些晦涩难懂的代码并没有什么实际作用。 - Gene

@Gene - 我并不认为>>=1是“晦涩难懂”的，但我认同您的观点，“清晰优于速度”，并修改了我的例子。同时，我利用这个机会修正了一个显眼的错误（temp>>msb应该是temp>>=msb）。 - Floris

建议将= 1<<msb;更改为= ((ulli)1)<<msb;。当sizeof(int) < sizeof(ulli)时，可能需要这样做。 - chux - Reinstate Monica

Answer 3

您可以使用 GCC内置函数 来完成此操作，如果您正在使用 GCC 进行编译的话。 内置函数 __builtin_clzll 可以计算无符号长长整型中前导零的数量。 您可以使用它来计算最高有效位的位置，然后将 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);

- Paul

---

我认为你想要使用 1LLU << ... 而不是 1。 - chux - Reinstate Monica

@chux 谢谢！我已经更新了。 - Paul

Answer 4

这篇经典的文档介绍了许多寻找整数的floor(log base 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标准。

- Gene

---

可能不是标准的C语言，但很酷！ - Floris

对于标准的C语言，只需使用int r; frexp(v, &r); r -= 1;。 - Eric Postpischil

Answer 5

我假设如果一个数字已经是2的幂或零，它应该保持不变并返回。仅适用于正数。

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添加到数字将设置最低位的零位。

- Mark Ransom

---

我需要花点时间思考，但现在我喜欢它了。不过它比二分查找更快吗？我认为它只能为非零位保存迭代次数；我是对的吗？ - Floris

@Floris，对的 - 它只跳过非零位。最好的情况是没有零位，最坏的情况是设置了2个位，其余都是零。二分查找可能更好。 - Mark Ransom

@bugsbunny的示例代码使用了无符号整数。我也问过关于另一个解决方案的问题，这种方法转换为无符号整数后，是否适用于MAX unsigned？（我担心的是n+1溢出——看起来它会立即退出while循环）也许对MAX UINT进行简单的测试可以解决问题。 - chux - Reinstate Monica

Answer 6

简短而精炼...
（问题者的示例代码在值>= 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;
  }
}

- chux - Reinstate Monica

---

这看起来很像问题中的“这是我尝试过的”示例，对吧？ - Floris

@Floris。同意，它确实很像这个例子。它需要两个更正：在while()之后执行>>=，并以正确的unsigned long long开始。因此，从算法上讲，这并没有增加讨论，但是发布的许多答案在算法上很有趣，但是在某些值方面存在问题。 SO中的许多问题都因为它们只涉及算法而被关闭。我解决了特定程序的弱点并提供了建议。顺便说一句，你的时间分析非常棒！测试是否也应包括针对ULLONG_MAX的正确性？ - chux - Reinstate Monica

Answer 7

这个问题与找到最高有效位的问题密切相关；因为在那之后只需要进行一些位移操作：

在此处详细描述了如何找到 MSB： 在位数组中查找设置的最高有效位（左侧） 然后你可以像这样做：

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

而且你已经拥有它了。

如果您使用英特尔架构，可以在gcc中使用__builtin_clz（计算前导零）来获取msb;

或者

这是一种非常有趣的方式，可以在没有CPU支持的情况下计算前导零。

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

- Ahmed Masud

---

我必须点赞这个超棒的hackersdelight链接！ - Floris

Answer 8

我知道递归通常不如迭代高效，但我情不自禁——我喜欢一个好的递归：

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

补充说明：实际计时表明，当使用优化编译时，这个版本比@LaurenceGonsalves的迭代版本略快。

- pjs

Answer 9

这比你的版本快大约两倍：

uint64_t g(uint64_t num) {
    uint64_t r = 1;
    num = num >> 1;
    while(num>r)   {
        r <<= 1;
    }
    return r;
}

- perreal

---

如果num > 0x8000000000000000LLU，则while循环不会终止。r达到值0x8000000000000000LLU将向左移动为0，然后循环继续进行。 - chux - Reinstate Monica

Answer 10

int test(int num) {
    int res = (num==0?0:1);
    while(num>1) {
        num=num>>1;
        res=res<<1;
    }
    return res;
}

当num不是很大时，比下面的更快。

- vvy

---

@bugsbunny没有说明对f(0)要做什么。只是注意到test(0)和test(1)都返回1。 - chux - Reinstate Monica

@chux 已经修复，但我不会考虑 num < 0 这种情况。 - vvy