编程之美--高效率算出1的数目之扩展问题

 1     public class NumberOfOne
 2     {
 3         public long Sum { get; set; }
 4         public void BinaryCount(int n)
 5         {
 6             CountLowest(n);
 7             CountCommont(n);
 8         }
 9 
10         public void CountLowest(int n)
11         {
12             //计算最低位(最右边位)1的总数
13             Sum = (n / 2) * 2 < n ? (n / 2) + 1 : Sum = n / 2;
14         }
15 
16         public void CountCommont(int n)
17         {
18             #region 开始计算除开最低位的1的总数
19             //比如说数列：1,2,3,4,4,4,1,2,3,4,4,4,1,2,3,4,4,4...，那么sequenceLength就是1,2,3的长度3，
20             //repeatLength就是4,4,4的长度（重复次数）3
21             long sequenceLength = 1;
22             long repeatLength = 3;
23             long exponent = 1;
24 
25             for (int i = 0; i < 32; i++)
26             {
27                 // exponent*2表示上面表格的每一列开头有多少个0，成2为幂底的指数增长
28                 long temp = (n + 1) - exponent * 2;
29                 if (temp <= 0)
30                 {
31                     break;
32                 }
33                 if (temp <= sequenceLength)
34                 {
35                     Sum += temp;
36                 }
37                 else
38                 {
39                     //组数
40                     long valueOfDivide = temp / (sequenceLength + repeatLength);
41                     long valueOfMockup = temp % (sequenceLength + repeatLength);
42 
43                     if (valueOfMockup <= sequenceLength)
44                     {
45                         //每组长度是sequenceLength+repeatLength，不过他们只有sequenceLength+1个不同的联系的值，
46                         //比如1,2,3,4,4这组有五个数，不过只有四个不同的连续的值：1,2,3,4。
47                         Sum += valueOfDivide * (sequenceLength + 1) + valueOfMockup;
48                     }
49                     else
50                     {
51                         Sum += valueOfDivide * (sequenceLength + 1) + sequenceLength + 1;
52                     }
53                 }
54                 exponent *= 2;
55                 sequenceLength += exponent;
56                 repeatLength += exponent;
57             }
58             #endregion
59         }
60 }

 1     class Program
 2     {
 3         static void Main(string[] args)
 4         {
 5             NumberOfOne numberOfOne = new NumberOfOne();
 6             while (true)
 7             {
 8                 int number = int.Parse(Console.ReadLine());
 9                 numberOfOne.BinaryCount(number);
10                 Console.WriteLine("0~{0}的所有二进制数的1的总和为：{1}", number, numberOfOne.Sum);
11 
12                 if (number == 444)
13                 {
14                     break;
15                 }
16             }
17             Console.ReadLine();
18         }
19     }