什么是计算(long int) ceiling(log_2(i))输入和输出为64位整数的快速方法？有符号或无符号整数的解决方案是可以接受的.我怀疑最好的方法将是一个类似于这里发现的方法,但不是尝试我自己,我想使用已经经过充分测试的东西.一般解决方案适用于所有正值.
例如,2,3,4,5,6,7,8的值为1,2,2,3,3,3,3
编辑:到目前为止,最好的路径似乎是使用任意数量的快速现有bithacks或寄存器方法计算整数/楼层日志基数2(MSB的位置),然后如果输入不是幂的话,则添加一个二.对2的幂的快速按位检查是(n&(n-1)).
编辑2:整数对数和前导零方法的一个很好的来源是亨利S.沃伦的Hacker's Delight中的第5-3和11-4节.这是我发现的最完整的治疗方法.
编辑3:这项技术看起来很有希望:https://stackoverflow.com/a/51351885/365478
感谢bit Twiddling的一些非常有用的stackOverflow用户:设置了哪个位？,我已经构建了我的函数(在问题的最后发布).
任何建议 - 即使是小建议 - 将不胜感激.希望它能使我的代码更好,但至少它应该教会我一些东西.:)
此函数将被调用至少10 13次,并且可能经常被调用10 15次.也就是说,此代码很可能会运行数月,因此任何性能提示都会有所帮助.
该功能占计划时间的72-77%,基于分析和不同配置中的大约十二次运行(优化这里不相关的某些参数).
此功能目前平均运行50个时钟.我不确定这可以改进多少,但我很高兴看到它在30岁时运行.
如果在计算的某个时刻你可以告诉你将返回的值很小(准确值可协商 - 比如说,低于一百万)你可以提前中止.我只对大价值感兴趣.
这就是我希望节省大部分时间的方式,而不是通过进一步的微观优化(尽管这些当然也是受欢迎的!).
添加以响应请求.您无需阅读此部分.
输入是奇数n,1 <n <4282250400097.其他输入提供了这个特定意义上的数字因子分解:
如果数字可被3整除,则设置smallprimes&1;如果数字可被5整除,则设置smallprimes&2;如果数字可被7整除,则设置smallprimes&4;如果数字可被11整除,则设置smallprimes和8,等等.表示313的有效位.可以用素数的平方整除的数字与仅被该数字整除的数字表示不同.(实际上,可以丢弃多个正方形;在另一个函数的预处理阶段,素数的多个正方形<= lim具有小的primes而q设置为0因此它们将被丢弃,其中lim的最佳值通过实验确定. )
q,r和s代表数字的较大因子.任何剩余因子(可能大于数字的平方根,或者如果s非零甚至可能更小)可以通过将因子除以n来找到.
一旦以这种方式恢复所有因子,使用由代码最佳解释的数学公式计算n为强伪荧光的碱基数1 <= b <n .
__attribute__ ((inline))什么都不做.奇怪的是,标记主要功能bases和一些助手__attribute ((hot))伤害性能几乎2%,我无法弄清楚为什么(但它可以重现超过20次测试).所以我没有做出改变.同样, …我使用"De Bruijn"算法来发现大数(最多64位)的二进制位数.
例如:
我发现使用基于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位)这是结果:
我试图理解"De Bruijn"是如何工作的,我该如何解决这个问题并为c#创建一个最终代码来计算多达64位的数字.
UDPATE和不同解决方案的基准
我正在寻找最快的算法来获得二进制数字的位数,无符号给定数量的64位在c#中(称为ulong).
例如:
传统的2和平方功率非常慢.只需10000次计算就需要1500ms才能得到答案.(100M计算需要数小时).
在这里,Niklas B., …
我试图找到一个最佳代码来定位长整数(64位)中的单个位索引.长整数只有一个设置位.(使用C语言)
目前,我只是将整个事情转移一点,然后检查零.我已经阅读了有关查找表的内容,但它不会对整个64位进行操作.我考虑过将每个8位检查为零,如果不使用查找,但我仍然需要一次移动8位.(换挡8比换挡8次要好？)
(注意:我正在为移动设备开发,它们[并不奇怪]慢).
正如所说。例如，对于 8 位（例如，不考虑字节顺序）整数 00100100（基数为 2），是否有指令给出 5？
我试图在任何地方找到解决方案.我的请求是找到一个非常快速的算法代码,以获得无符号64位积分器(ulong)的二进制表示中的位数.
例如:
127 = 7 binary digits.
153 = 8 binary digits.
我现在找到了两种方法来获得这个.
两种方式都很好,但是当数量很大时,计算时间太长.在10.000.000.000(10亿)之后,你必须计算花费的时间,而不是毫秒,这对于其余代码的性能来说是如此糟糕.
非常感谢并且对于演示文稿感到抱歉,这是用手机写的,我没有所有的工具来把这个更好的和正确的.
编辑1
通过深入了解Bithacks网站并将速度作为首要任务.我想我将使用具有De Bruijn序列实现的Lookup表方法.
正如我在这里找到的:具有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
};
在此基础上,用户"R .."从#1,他让自己的paramether,在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位)