从左往右处理,左半部分记为left, 右半部分记为right,若i,i -1均为1, 贡献为ans += (left + 1) + right * (1ll << (i - 1));
否则贡献为ans += right * (1ll << (i - 1));
import java.math.BigInteger; import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner cin = new Scanner(System.in); int t = 0; while(cin.hasNext()){ BigInteger n = cin.nextBigInteger(); if(n.compareTo(BigInteger.ZERO) < 0){ break; } long cnt = n.toString(2).length(); BigInteger right = n.shiftRight(2), left = BigInteger.ZERO; BigInteger ans = BigInteger.ZERO; for(long i = 1; i < cnt; i++){ if(n.testBit((int)i) && n.testBit((int)i - 1)){ ans = ans.add(left.add(BigInteger.ONE)).add(right.multiply(BigInteger.ONE.shiftLeft((int)i - 1))); //ans += (left + 1) + right * (1ll << (i - 1)); }else{ ans = ans.add(right.multiply(BigInteger.ONE.shiftLeft((int)i - 1))); //ans += right * (1ll << (i - 1)); } right = right.shiftRight(1); if(n.testBit((int)i - 1)){ left = left.add(BigInteger.ONE.shiftLeft((int)i - 1)); } //left |= n & (1ll << (i - 1)); } System.out.printf("Case %d: ", ++t); System.out.println(ans); } System.exit(0); } }