投資錢景>買台積電就對了工程師靠存股年領百萬股息攝影界美人正妹指定相機款買太多也不行!7500...
2013-02-28 08:16:48 人氣(403) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][遞迴] 12208 - How Many Ones Needed?

0
收藏
0
推薦

 

To write binary numbers we need only two digits ‘0’ and ‘1’. To write a specific value we need a fixed number of ones, but of course number of zeroes may vary because of leading zeroes. For example to write values between 5 and 10 (inclusive) we need total 12 ones as shown in the figure on the left. You have to write a program that finds total number of ones that are required to write numbers in binary within a given range a and b.

 

Input

The input file can contain up to 11000 lines of inputs. Each line contains two positive integers a and b (0 ≤ a ≤ b ≤ 2000000000).

 

Input is terminated by a line containing two zeroes. This line should not be processed.

 

Output

For each line of input of input produce one line of output. This line contains the serial of output followed by an integer which denotes the number of ‘1’ s required to write all the values between a and b (inclusive) in binary. Look at the output for sample input for details.

 

Sample Input                              Output for Sample Input

5 10

20 30

0 0

Case 1: 12

Case 2: 35

 





遞迴要怎麼推呢?不仿列一下前幾個二進制
00000
00001
00010
00011
00100
00101
00110
00111
01000

先看位數
1. 1位數 = 1
2. 2位數 = 4
3. 3位數 = 12
... 得到 digit[i] = digit[i-1]*2 + 2^(i-1)
這很好推的,發現最高位只有一半是1,而後面個數等同少一位的。

假使我們要求 n = 5, (101), 她是一個3位數的二進制數,
馬上可以知道2位所用的 1 的個數, 把三位的一去掉, 然後去求剩餘兩位的值。



#include <stdio.h>
long long digit[50] = {1};

long long cntOnes(long long n) {
    if(n < 1)  return 0;
    if(n == 1)  return 1;
    long long sum = 0;
    int i, high_bit;
    for(i = 0; i < 40; i++) {
        if((n>>i)&1)
            high_bit = i;
    }
    if(high_bit)
        sum += digit[high_bit-1];
    return sum + (n-(1LL<<high_bit)+1) + cntOnes(n-(1LL<<high_bit));
}
int main() {
    int i, cases = 0;
    long long a, b;
    for(i = 1; i < 50; i++)
        digit[i] = (digit[i-1]<<1) + (1<<i);
    while(scanf("%lld %lld", &a, &b) == 2) {
        if(a == 0 && b == 0)
            break;
        printf("Case %d: %lld\n", ++cases, cntOnes(b)-cntOnes(a-1));
    }
    return 0;
}

12208How Many Ones Needed?
台長:Morris
人氣(403) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][queue] 12100 - Printer Queue
此分類上一篇:[UVA][?] 12207 - That is Your Queue

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文