python - 为什么我总是少一分

Question

我正在解决 problem在 Codeforce 中，这是我之前提交的

#!/usr/local/bin/python

limit = 10**18
string = raw_input()
year1, year2 = string.split()
year1 = int(year1)
year2 = int(year2)
x = 1
count = 0
a = []
while True:
    k = 2**x - 1

    if k > limit:
        break
    else:
        for i in xrange(len(bin(k)[2:])):
            if year1 <= k - (1 << i) <= year2 and len(bin(k - (1 << i))[2:].split('0')) == 2:
                count += 1
    x += 1
print count

它适用于所有给定值，但它在 1 到 1000000000000000000 范围内给出的计数值少了一个。很难调试，因此我在最后一个 print 之前放了一段破解代码，就像这样

if year2 - year1 + 1 == limit:
    count += 1

它适用于该值，但对于另一个范围，1 到 935829385028502935 再次给出一个较小的值。

难怪 logic-less hack 没有起作用，但我想知道为什么它以前少了一个计数值？

Answer 1

你需要增加limit另一个数量级:

limit = 10**19

否则你会错过 864691128455135231 , 从 1152921504606846975 - (1 << 58) 获得.

(观察 1152921504606846975 > 10**18 。)