Description

The cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone’ (also known as ‘Rock, Paper, Scissors’, ‘Ro, Sham, Bo’, and a host of other names) in order to make arbitrary decisions such as who gets to be milked first. They can’t even flip a coin because it’s so hard to toss using hooves.

They have thus resorted to “round number” matching. The first cow picks an integer less than two billion. The second cow does the same. If the numbers are both “round numbers”, the first cow wins, otherwise the second cow wins.

A positive integer N is said to be a “round number” if the binary rePResentation of N has as many or more zeroes than it has ones. For example, the integer 9, when written in binary form, is 1001. 1001 has two zeroes and two ones; thus, 9 is a round number. The integer 26 is 11010 in binary; since it has two zeroes and three ones, it is not a round number.

Obviously, it takes cows a while to convert numbers to binary, so the winner takes a while to determine. Bessie wants to cheat and thinks she can do that if she knows how many “round numbers” are in a given range.

Help her by writing a program that tells how many round numbers appear in the inclusive range given by the input (1 ≤ Start < Finish ≤ 2,000,000,000).

Input

Line 1: Two space-separated integers, respectively Start and Finish. Output

Line 1: A single integer that is the count of round numbers in the inclusive range Start..Finish Sample Input

2 12 Sample Output

6

題目大意 輸入兩個數s、e，在[s,e]中有多少個數的二進制表示形式滿足round number，即滿足其二進制表示中 0 的數目大于或等于 1 的數目。

解題思路 首先，根據區間減法，將求解[s,e]區間的問題轉化為求解[1,e+1]-[1,s]區間的問題； 對于一個十進制數x，先將其轉化為二進制數，得其位數length，將滿足條件的結果分為兩部分來求： 1、位數小于length。滿足條件的值有：對于每個小于length的位數 i ，至少需要填補 （i/2+1） 個 0，至多全為 0 。 2、位數與length相等。對于二進制序列由右至左進行檢索（i 標記），若該位為0，標記0的個數zero +1；若該位為1，則先假設該位變為 0，那么無論右側每位 1，0 取值如何，其值都小于x，即滿足條件。滿足條件的值有：在右側的數位（即 i-1）中，至少需要填補（length+1）/2-（zero+1）個 0（zero+1加的是當前檢索到的該位已由 1 變為 0 ），至多 i-1 個全為 0 。

代碼實現