1

我试图在任何地方找到解决方案。我的要求是找到一个非常快速的算法代码，以便获取无符号 64 位整数（ulong）的二进制表示中的位数。

例如：

127 = 7 binary digits.

153 = 8 binary digits.

我现在找到了两种方法来获得这个。

  • 通过在字符串中修剪二进制表示，并使用“.Length”属性。
  • 通过获得不通过数字的 2 的最大幂。结果是二进制表示的最后一个位置，如果加上 1（表示 2^0），还表示位数

两种方式都很好，但是当数字很大时计算时间太长。在 10.000.000.000（100 亿）之后，您必须以秒而不是毫秒为单位计算所花费的时间，这对其余代码的性能非常不利。

非常感谢和抱歉关于演示文稿，这是用手机写的，我没有所有工具来把这个更漂亮和更正确。

编辑 1

通过深入了解Bithacks网站并将速度作为第一要务。我想我将在De Bruijn 序列实现中使用查找表方法。

正如我在这里发现的那样：2^6 的 64 位查找表应该是这样的。

static readonly int[] MultiplyDeBruijnBitPosition2 = new int[64]
{
  0,1,2,4,8,17,34,5,11,23,47,31,63,62,61,59,
  55,46,29,58,53,43,22,44,24,49,35,7,15,30,60,57,
  51,38,12,25,50,36,9,18,37,10,21,42,20,41,19,39,
  14,28,56,48,33,3,6,13,27,54,45,26,52,40,16,32
};

基于此，来自 Stackoverflow 的用户“R..”，他制作了自己的参数，在 C# 中应该是这样的：

public static int GetLog2_DeBruijn(ulong v)
{
return MultiplyDeBruijnBitPosition2[(ulong)(v * 0x022fdd63cc95386dull) >> 58];
}

结果确实很快但错误，我不知道为什么。PD：如您所见，“0x022fdd63cc95386dull”用于 128 位，C# 的可接受代码为“0x022fdd63cc95386d”。与此处的查找表中出现的相同。

我认为因为我不能在 C# 中使用“0x022fdd63cc95386dull”，所以我必须使用另一个数字而不是 58，或者可能是一个完全不同的十六进制 64 位乘法器。

至此，对于输入数字：17012389719861204799（使用 64 位）

  • 使用 pow2 方法，我在 1380 毫秒内得到了 64 1 百万次的结果。
  • 使用 DeBruijn 方法，我在 32 毫秒内得到了 40 1 百万次的结果。（不知道为什么40）
4

2 回答 2

5

根据bit twiddling hack page，您可以找到如下设置的最高位：

uint v;
uint r;
uint shift;

r =     (uint)((v > 0xFFFF) ? 1 : 0) << 4; v >>= (int)r;
shift = (uint)((v > 0xFF  ) ? 1 : 0) << 3; v >>= (int)shift; r |= shift;
shift = (uint)((v > 0xF   ) ? 1 : 0) << 2; v >>= (int)shift; r |= shift;
shift = (uint)((v > 0x3   ) ? 1 : 0) << 1; v >>= (int)shift; r |= shift;
                                        r |= (v >> 1);
// At this point r has the result

这是ideone的演示。

于 2014-02-18T02:33:52.903 回答
0

尝试平方2到小于您正在考虑的数字的最大值。然后移动该数字计数（平方步骤2^n后的数字n），并重复，沿途对数字计数求和。这应该是一个订单log log n流程。

于 2014-02-18T02:35:17.003 回答