CYOI第九届欢乐赛 BT

将一个二进制数最右边的1之前的部分去掉余下部分称为这个数的二进制尾部,例如6(110)2的二进制尾部为2(10)2  40(101000)2的二进制尾部为8(1000)2

写一程序计算A到B之间所有数的二进制尾部总和

输入

输入文件仅一行包含两个用空格隔开的整数AB,其中1≤A≤B≤1015

输出

输出文件仅一行包含一个整数表示要求的二进制尾部和。注意答案不超过64位二进制整数Pascal中的int64C/C++中的long long。

样例

Input

5 9

Output

13

 

大体思路就是计算出A-B中有多少个数的Lowbit是Kdec 然后把所有的 K 和 个数 相乘即可。

每隔四个数出现一次lowbit为2的数

每隔八个数出现一次lowbit为4的数

依此类推 则有

所以还需要打一个lowbit的表就行了

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据