2014-05-03

UVa 12670 - Counting ones

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

Carl is right now the happiest child in the world: he has just learned this morning what the binary system is. He learned, for instance, that the binary representation of a positive integer k is a string a[n], a[n-1], …, a[0] where each a[i] is a binary digit 0 or 1, starting with a[n] = 1, and such that k = \sum{i = 0, n} a[i] * 2^ i. It is really nice to see him turning decimal numbers into binary numbers, and then adding and even multiplying them.

Caesar is Carl’s older brother, and he just can’t stand to see his little brother so happy. So he has prepared a challenge: \Look Carl, I have an easy question for you: I will give you two integers A and B, and you have to tell me how many 1’s there are in the binary representation of all the integers from A to B, inclusive. Get ready”. Carl agreed to the challenge. After a few minutes, he came back with a list of the binary representation of all the integers from 1 to 100. \Caesar, I’m ready”. Caesar smiled and said: \Well, let me see, I choose A = 10^15 and B = 10^16. Your list will not be useful”.

Carl hates loosing to his brother so he needs a better solution fast. Can you help him ?

Input

The input file contains several test cases, each of them as described below.
A single line that contains two integers A and B (1 <= A <= B <= 10^16).

Output

For each test case, output a line with an integer representing the total number of digits 1 in the binary representation of all the integers from A to B, inclusive.

Sample Input

1
2
3

1000000000000000 10000000000000000
2 12
9007199254740992 9007199254740992

Sample Output

1
2
3

239502115812196372
21
1

Solution

題目描述：
計算 A 到 B 之間的二進制數出現了幾次 1。

題目解法：
將問題轉換成計算 0 到 A 出現了幾次 1，接著討論在相同長度下 1 出現的次數，之後再遞歸求解。

討論的時候，考慮長度為 n 時，每一位的填法，計算要看切割位置的前半和後半數字，詳細查閱代碼。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long mpow(int n, int m) {
    long long ret = 1;
    for(int i = 1; i <= m; i++)
        ret *= n;
    return ret;
}
void ito2(long long n, char buf[]) {
    if(n == 0) {
        buf[0] = '0';
        buf[1] = '\0';
        return;
    }
    int i, j, f;
    for(i = 63, j = f = 0; i >= 0; i--) {
        if((n>>i)&1)	f = 1;
        if(f) {
            buf[j++] = ((n>>i)&1) + '0';
        }
    }
    buf[j] = '\0';
}
void a2toi(long long &r, char buf[]) {
    r = 0;
    for(int i = 0; buf[i]; i++)
        r = r<<1 | (buf[i] - '0');
}
void calc(long long n, long long cnt[]) {
    if(n <= 0)
        return;
    //printf("%d\n", n);
    char buf[105];
    ito2(n, buf);
    int len = strlen(buf);
    long long prev = 0;
    long long suffix;
    calc(mpow(2, len-1)-1, cnt);
    //for(int i = 0; i < 10; i++)
    //	cnt[i] = 0;
    long long prev10 = 1;
    for(int i = 0; i < len; i++) {
        int d = buf[i] - '0';
        a2toi(suffix, buf + i + 1);
        
        if(i != len-1)
            cnt[d] += suffix + 1;
        else
            cnt[d]++;
        if(i != 0)
            cnt[d] += (prev - prev10/2) * mpow(2, len-i-1);
        for(int j = i == 0; j < 2; j++) {
            if(j == d)	continue;
            if(j < d) {
                if(prev > 0) {
                    cnt[j] += (prev - prev10/2 + 1) * mpow(2, len-i-1);
                } else {
                    cnt[j] += mpow(2, len-i-1);
                }
            } else {
                if(prev > 0 && prev - prev10/2 > 0) {
                    cnt[j] += (prev - prev10/2) * mpow(2, len-i-1);
                }
            }
        }
        prev10 *= 2;
        prev = prev * 2 + d;
    }
}
int main() {
    long long A, B;
    while(scanf("%lld %lld", &A, &B) == 2) {
        long long cntA[2] = {}, cntB[2] = {};
        calc(A - 1, cntA);
        calc(B, cntB);
        printf("%lld\n", cntB[1] - cntA[1]);
    }
    return 0;
}

Morris' Blog