1.

import java.math.BigInteger;
import java.util.Scanner;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 11645 Bits
* Link:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=78&problem=2692&mosmsg=Submission+received+with+ID+7613502
*
* @author Kratzer Kevin
* @version 1.0, 12/09/2009
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.580
*/

public class Main11645 {
private final static BigInteger[] numbers = new BigInteger[64];
private final static BigInteger two = BigInteger.valueOf(2);
public static BigInteger n(int i) {
switch(i) {
case 0:
case 1:
return BigInteger.ZERO;
default:
return (numbers[i-1].multiply(two)).add(BigInteger.valueOf(2).pow(i-2));
}
}

public static void main(String... args) {
for(int i = 0; i < 64; i++) {
numbers[i] = n(i);
}
long curCase = 1;
Scanner s = new Scanner(System.in);
for(BigInteger number = s.nextBigInteger(); number.compareTo(BigInteger.ZERO) >= 0; number = s.nextBigInteger()) {

int index = number.bitLength();


BigInteger maxNumber = BigInteger.ONE.shiftLeft(index);
BigInteger distance = (maxNumber.subtract(BigInteger.ONE)).subtract(number);
System.out.println("Case " + curCase + ": " + getRemaining(number, maxNumber, distance, index));
curCase++;
}
}

private static BigInteger getRemaining(BigInteger number, BigInteger maxNumber, BigInteger distance, int index) {
if(index<2){
return numbers[0];
}
if(distance.equals(BigInteger.ZERO)) {
return numbers[index];
} else if(distance.equals(maxNumber.shiftRight(2))) {
return numbers[index-1].add(numbers[index-2]);
} else {
int newIndex = index-1;
BigInteger newNumber = number;
if(number.testBit(newIndex)) {
newNumber = number.flipBit(newIndex);
}
BigInteger newMaxNumber = maxNumber.shiftRight(1);
BigInteger newDistance = (newMaxNumber.subtract(newNumber)).subtract(BigInteger.ONE);
BigInteger add = BigInteger.ZERO;

if(number.compareTo(newMaxNumber) >= 0) {
add = numbers[index-1];
}

if(distance.compareTo(maxNumber.shiftRight(2)) > 0) {
return add.add(getRemaining(newNumber,newMaxNumber,newDistance,newIndex));
} else {
return add.add((((maxNumber.shiftRight(2)).subtract(distance).add(getRemaining(newNumber,newMaxNumber,newDistance,newIndex)))));
}
}

}
}
/**************************************************************************
0 0
1 0

-

00 0
01 0

10 0
11 1

-

000 0
001 0

010 0
011 1

100 0
101 0

110 1
111 2

-

0000 0
0001 0

0010 0
0011 1

0100 0
0101 0

0110 1
0111 2



1000 0 7
1001 0 6

1010 0 5
1011 1 4

1100 0+1 3
1101 0+1 2

1110 1+1 1
1111 2+1 0


------------------------

00000 0
00001 0
00010 0
00011 1
00100 0
00101 0
00110 1
00111 2

01000 0
01001 0
01010 0
01011 1
01100 0+1
01101 0+1
01110 1+1
01111 2+1



10000 0
10001 0
10010 0
10011 1
10100 0
10101 0
10110 1
10111 2

11000 0+1
11001 0+1
11010 0+1
11011 1+1
11100 0+1+1
11101 0+1+1
11110 1+1+1
11111 2+1+1

n(1) = 0
n(2) = 2n(1) + 2^(2-2)
n(3) = 2n(2) + 2^(3-2)
n(k) = 2n(k-1) + 2^(k-2)
**************************************************/