关于一个运算优化的问题

litaoye

原帖由 无心人 于 2009-3-13 16:37 发表 楼主的这个结论是错误的： 如果最高位m高于10^n,且低于10^n+1，那么这个数同最高位小于m的数进行Xor并取log10后的结果，都是n，

10^20 - 2^20的最高位同10^20是相等的,并不高于10^20,我说的是高于,不包括等于,等于的情况必须要逐个计算

无心人

我还能构造出 B << A log(A XOR B) < log(A)的例子来 呵呵

无心人

To 81# 等于的情况占38 / 128 也太多了点

litaoye

现在是0.34秒跑到Test#10出错了,对于c#,0.34应该还可以,一个A+B都需要0.125呢,呵呵!

无心人

To 81# 我修改了那个回复 虽然你的说法没错误 也不妥当，容易引起误解

litaoye

原帖由 无心人 于 2009-3-13 16:45 发表 To 81# 等于的情况占38 / 128 也太多了点

是呀,等于的情况确实不少,因此这种优化能够减少的计算量有限,且不可预测,所以未必是一种好的方法! 不过如果数据差异较大,效果还是过的去。

litaoye

呵呵，能帮我改一下最好了！

gxqcn

如果两整数分别为 a, b（a≥b），其 bit 数相差不小于 d， 则取较大者数 a 的前 d 位（bit数）， 然后左移 r 位使之与 a 位数相等，记该数为 x。 显然 $b < 2^r <= x <= a$， 则两数XOR后：$x <= a\quad"XOR"\quadb <= x + 2^r - 1$ 所以，若 $10^k <= x <= 10^(k+1)-2^r$ 则可保证两数XOR后的LOG10结果为 k.

无心人

都是为了避免对数运算吧 看宝宝的对数汇编出来后 对数运算占多少的比重就知道了

liangbch

今天是没有时间搞了，到星期天，看看能不能完成。 To 楼主，使用C# 确实吃亏，C#应该没有C++ 和汇编混合编程来的快些。楼主可考虑用C++编程。