擅长:python、mysql、java
<p>你可能需要一种不同的方法,而不仅仅是像John那样的小改进。我刚刚在我的电脑上写了一个可以在大约2秒钟内完成<code>answer(0, 50000)</code>的解决方案。我仍然逐行执行,但是我没有对行范围内的所有数字执行xooring,而是一点一点地执行。行中有多少个数字设置了1位?<sup>[*]</sup>奇数?然后我把我的答案翻过来。对于2位、4位、8位等,则相同,直到2<sup>30</sup>-位。因此,对于每一行,它只是31个小计算(而不是实际的xooring数万个数字)。在</p>
<p>[*]可以在固定时间内快速计算,只需从范围的开始/停止。在</p>
<p><strong>编辑:</strong>既然您要求了另一个提示,下面就介绍如何计算在某个范围(a,b)内设置1位的频率。计算它在范围(0,a)中设置的频率,并从它在范围(0,b)中设置的频率中减去。如果范围从零开始就容易多了。在某个范围(0,c)内设置1位的频率是多少?简单:<code>c//2</code>次。那么在某个范围(a,b)中1位的设置频率是多少?只需<code>b//2 - a//2</code>次。更高的位是相似的,只是稍微复杂一点。在</p>
<p><strong>编辑2:</strong>哦,等等,我刚刚想起。。。有一种简单的方法可以计算某个范围(a,b)内所有数的异或。再次将工作分成范围(0,a)和范围(0,b)。在某个范围(0,c)内所有数字的异或很容易,因为有一个很好的模式(如果你对0到30的所有c都这样做,你就会看到它)。使用这个方法,我现在可以在大约<strong>0.04秒内求解<code>answer(0, 50000)</code>。在</p>