相关疑难解决方法(0)

如何计算Int32中的前导零？所以我想要做的是写一个函数,如果我的输入Int32是2则返回30,因为在二进制中我有0000000000000010.

我使用"De Bruijn"算法来发现大数(最多64位)的二进制位数.

例如:

• 1022具有10位二进制数字.
• 130有二进制8位数.

我发现使用基于De Bruijn的表查找让我有能力比传统方式(功率,方形......)计算x100倍.

根据该网站,2 ^ 6具有用于计算64位数的表.这将是c#中暴露的表

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

(我不知道我是否正确地从该网站带来了桌子)然后,根据R ..评论这里.我应该使用它来使用带有输入uint64号的表.

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

但是c#编译器不允许我使用" 0x022fdd63cc95386dull ",因为它溢出了64位.我必须使用" 0x022fdd63cc95386d "代替.

使用这些代码.问题是我没有得到给定输入的正确结果.

例如,做1.000.000计算的数字:17012389719861204799(使用64位)这是结果:

• 使用pow2方法我在1380ms内得到64百万次的结果.
• 使用DeBruijn方法,我在32ms内得到结果40百万次.(不知道为什么40)

我试图理解"De Bruijn"是如何工作的,我该如何解决这个问题并为c#创建一个最终代码来计算多达64位的数字.

UDPATE和不同解决方案的基准

我正在寻找最快的算法来获得二进制数字的位数,无符号给定数量的64位在c#中(称为ulong).

例如:

• 1024有11位二进制数字.(2 ^ 10 + 1)或(log2 [1024] +1)
• 9223372036854775808有64位二进制数字.(2 ^ 63 + 1)或(log2 [2 ^ 63] +1)

传统的2和平方功率非常慢.只需10000次计算就需要1500ms才能得到答案.(100M计算需要数小时).

在这里,Niklas B., …

什么是从最低有效位(LSB)到ulong(C#)中的最高有效位(MSB)的第一个设置(1)位位置的最快(或至少非常快)的方法？对于ulong i = 18; (10010),将为2(如果我们从0开始计算位置,则为1).

MS C++编译器具有 _BitScanForward64用于此任务的内在函数,但C#编译器没有模拟.