计算快速对数基数 2 上限 [英] Compute fast log base 2 ceiling

问题描述

计算 (long int)天花板(log_2(i)) 的快速方法是什么，其中输入和输出是 64 位整数?有符号或无符号整数的解是可以接受的.我怀疑最好的方法是类似于在 here，但与其尝试自己的尝试，我更愿意使用已经过充分测试的东西.通用解决方案适用于所有正值.

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 的位置)，然后如果输入不是则添加一个二的幂.对 2 的幂的快速按位检查是 (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)).

编辑 2:关于整数对数和前导零方法的一个很好的来源是 Hacker's Delight 中的第 5-3 节和第 11-4 节 作者:亨利·S·沃伦.这是我找到的最完整的治疗方法.

Edit 2: A good source on integer logarithms and leading zeroes methods is Sections 5-3 and 11-4 in Hacker's Delight by Henry S. Warren. This is the most complete treatment I've found.

编辑 3:这种技术看起来很有前景:https://stackoverflow.com/a/51351885/365478 >

Edit 3: This technique looks promising: https://stackoverflow.com/a/51351885/365478

推荐答案

这个算法已经贴出来了，但是下面的实现很紧凑，应该优化成无分支代码.

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
", ceil_log2(atol(argv[1])));

  return 0;
}

这篇关于计算快速对数基数 2 上限的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！