计算速度快的日志基地2天花板 [英] Compute fast log base 2 ceiling

查看:267
本文介绍了计算速度快的日志基地2天花板的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

什么是一个快速的方法来计算(长整型)上限(log_2(I)),其中输入和输出的64位整数?为符号或无符号的整数解决方案是可接受的。我怀疑最好的办法将类似于这里那些被发现一个位变换的方法,但不是尝试我自己的,我想使用一些已经行之有效的。一般的解决方案将适用于所有正面的价值观。

What is a fast way to compute the (long int) ceiling(log_2(i)), where the input and output are 64-bit integers? Solutions for signed or unsigned integers are acceptable. I suspect the best way will be a bit-twiddling method similar to those found here, but rather than attempt my own I would like to use something that is already well tested. A general solution will work for all positive values.

有关例如,对于2,3,4,5,6,7,8的值是1,2,2,3,3,3,3

For instance, the values for 2,3,4,5,6,7,8 are 1,2,2,3,3,3,3

编辑:到目前为止的最佳路线似乎是计算使用任何数目的快速现有bithacks整数/楼层数底2(与MSB的位置)或寄存器方法,然后添加一个如果输入是不二的幂。快速按位检查的两个大国是。(N及(N-1))

So far the best route seems to be to compute the integer/floor log base 2 (the position of the MSB) using any number of fast existing bithacks or register methods, and then to add one if the input is not a power of two. The fast bitwise check for powers of two is (n&(n-1)).

另一种方法可能会尝试在指数二进制搜索电子直到 1<&LT,E 大于或等于输入。

Another method might be to try a binary search on exponents e until 1<<e is greater than or equal to the input.

推荐答案

这个算法已经被公布,但下面的实现是非常紧凑的,应该优化成支自由code。

This algorithm has already been posted, but the following implementation is very compact and should optimize into branch-free code.

int ceil_log2(unsigned long long x)
{
  static const unsigned long long t[6] = {
    0xFFFFFFFF00000000ull,
    0x00000000FFFF0000ull,
    0x000000000000FF00ull,
    0x00000000000000F0ull,
    0x000000000000000Cull,
    0x0000000000000002ull
  };

  int y = (((x & (x - 1)) == 0) ? 0 : 1);
  int j = 32;
  int i;

  for (i = 0; i < 6; i++) {
    int k = (((x & t[i]) == 0) ? 0 : j);
    y += k;
    x >>= k;
    j >>= 1;
  }

  return y;
}


#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
  printf("%d\n", ceil_log2(atol(argv[1])));

  return 0;
}

这篇关于计算速度快的日志基地2天花板的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆