如何得到一个范围内二进制表示中正好有2个1的数的和？

Question

我想找出一个范围内的数字之和，比如说N，在它的二进制表示中正好有2个1

N = int(raw_input())
sum1 = 0
for i in range(1, N + 1):
    if bin(i)[2:].count('1') == 2:
       sum1 = sum1 + i

这个代码需要很多时间。有没有更快的方法来做这个计算？你知道吗

Answer 1

如果我们看一下如何找到用二进制写时有两个“1”的数，我们得到两种情况：

• 在二进制表示中，我们有一个元素>；1和1'1'，然后加上1
• 我们有一个元素，在二进制表示中有两个'1'，我们把它乘以2。你知道吗

因此，要查找与此情况匹配的元素数，可以执行以下操作：

num = int(raw_input())
def get_numbers(N):
    sum1 = []
    sum2 = []
    i = 2
    while i < N:
        # we add the elements of case 2
        sum1.extend(sum2)
        # we add the element of case 1
        sum1.append(i+1)
        sum2 = [2*x for x in sum1 if x > i]
        # we check for the elements with one more number when written in binary
        i *= 2
    # sum1 now contains all elements with two '1' in binary between 0 and the power of 2 above N.
    # we remove the elements above N
    sum1 = [x for x in sum1 if x <= N]
    # we sort the list
    sum1.sort()
    # we take the length of the list, of the number of elements with two '1' in binary between 0 and N
    return sum1

 print(get_numbers(num))

这应该更快，因为我们不会测试0和N之间的每个数字，并且具有log2（N）复杂性。你知道吗

如果你对我的方法有任何疑问，请不要犹豫。你知道吗

此方法比另一个答案中的方法慢（大约慢2倍）

Answer 2

请尝试以下代码：

def two_bit_numbers(N):
    bit0 = 0
    bit1 = 1
    while True:
        n = (1<<bit1) + (1<<bit0)
        if n > N:
            break
        yield n
        bit0 += 1
        if bit0 == bit1:
            bit1 += 1
            bit0 = 0

N = 100
sum1 = 0

for i in two_bit_numbers(N):
    # print i, bin(i)
    sum1 += i

print sum1