【每日一题20220715】数数1有几个

兴趣爱好交流 每日一题
1

:mage:‍ 给定两个数字： ‘left’ 和 ‘right’ (1 <= ‘left’ <= ‘right’ <= 200000000000000) 返回在 ‘left’ 和 ‘right’ 之间的数字的二进制表示中出现的所有 ‘1’ 的总和（前闭后闭区间）

例如:
count_ones(4,7) 返回值为 8, 因为:
4(十进制) = 100(二进制), 有一个1.
5(十进制) = 101(二进制), 有两个1.
6(十进制) = 110(二进制), 有两个1.
7(十进制) = 111(二进制), 有三个1.
所以最终返回值为 8

警告：数字区间可能包含十亿到上千亿个数字，所以解决方案不能遍历段中的所有数字！

题目难度：偏难
题目来源：https://www.codewars.com/kata/596d34df24a04ee1e3000a25


def count_ones(left, right):
    # your code here

assert count_ones(4,7) == 8
assert count_ones(1, 1000) == 4938
assert count_ones(1, 10000) == 64613
assert count_ones(89000000000,191000000000000) == 4490486865439510
assert count_ones(1, 200000000000000) == 4712825299386385
2

image
image1842×842 98.4 KB

3 
def count_ones(left, right):
    return count(right) - count(left-1)
def count(n):
    s = 0
    while n>0:
        #bit_length内置函数，求某个十进制数的二进制的长度，这里是去掉0b后的长度
        p = n.bit_length()-1 
        #p2是2**(n的二进制位数减一)
        p2 = 1<<p  
        #n与2**(n的二进制位数减一) 之间的距离
        n -=  p2  
        #p*(p2>>1) 表示 2的p次幂内1的个数，即p*(2**(p-1))
        s += p*(p2>>1) + 1 + n 
    return s