Tecent-1016-4.cpp

    // 小Q按如下方式构造一个01串：
    // 第一个字符是1第二个字符是0，此时字符串为"10"
    // 第3~4个字符，为前两个字符的零一翻转 （1变0，0变1），此时字符串为"1001" 
    // 第5~8个字符，为第1~4个字符的零一翻转， 此时字符串为10010110" 
    // 第9~16个字符，为第1~8个字符的零一翻转， 此时字符串为1001011001101001" 
    // 后面的操作同理。
    // 小Q按这个方法构造了一个无限长的串。 她想知道，第L个字符到第 R 个字符形成的子串中，一共有多少个'1'？
    //4 7   输出 3
//2^n == R 时，0 ~ R 有一半个1，  
//计算出2^x > R 则  2^x-1 <= R  R 由 2^x-1 和 R - 2^x-1 两部分组成  前者一半个1  后者递归计算，递归到第一个元素时 可能为1 也可能为0

#include<iostream>

using namespace std;

long long cal(int num, int bit){
    if(num == 0) return 0;
    if(num == 1) return bit;  //递归计算 后半部分 可能为1  也可能为0
    if(num == 2) return 1;  //2^n  必然一半  1个1
    int x = 0;
    while((1 << x) <= num) ++x;
    --x;  //此时2^x <= num
    num -= 1 << x;  //减去前一部分 剩下的参与递归计算
    int ans = 0;
    if(x > 0)
        ans += 1 << (x - 1);   //计算出前一部分1的个数
    return ans + cal(num, 1 - bit);  //前一整部分 和  后半部分

}

int main(){
    int L, R;
    cin >> L >> R;
    cout << cal(R, 1) - cal(L - 1, 1);
    // cout << cal(R, 1) << endl;
    // cout << cal(L - 1, 1);
}