题目链接：http://www.topcoder.com/stat?c=problem_statement&pm=10408&rd=13747最终的水要放在K个瓶子里面，而每个瓶子中的水的数量必须为2的整数幂，即最终的水数量n'要能分解成
k个2的整数幂，也就是new_n的二进制表示中1的个数要<=k.
用count(n)表示n的二进制表示中1的个数，如果count(n)<=k，那就不需要买瓶子了。
如果count(n)>k，说明我们要找到第一个n'使得n'>n并且count(n')<=k。那就是说我们要减少n中1的个数。
我们把n表示为x0ab.其中a为全1,b为全0. a,b的长度>=0.
很明显，第一个减少1的个数的n'应该为x1{(a+b)个0}，也就是把ab全部变成0.ab前的0变为1.即加上一个1<<length(b).
因为对b来说，无论增加多少都会增加1的个数。
然后再判断n'的1的个数，直到count(n)<=k。
因为n最大为10^7，n'最大为10^8，int类型不会溢出。因此边界条件就无需判断了。
1 #include <vector>
2 #include <algorithm>
3 #include <sstream>
4 #include <string>
5 #include <iostream>
6
7 using namespace std;
8
9 int count(int i)
10 {
11 int res = 0;
12 while(i!=0){
13 i&=(i-1);
14 res++;
15 }
16
17 return res;
18 }
19
20 class PouringWater
21 {
22 public:
23 int getMinBottles(int N, int K)
24 {
25 int res = 0;
26 int mask = 1;
27
28 while(count(N)>K){
29 //找到第一个1...第n次犯了没把N&mask括号括起来的错误了。。。&的优先级<等号...
30 while( (N&mask)==0) mask<<=1;
31 //加上mask使得1的数目减少
32 N+=mask;
33 res += mask;
34 }
35
36 return res;
37 }
38
39