[UVA][遞迴] 12208 - How Many Ones Needed?
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;
}