Question

This question already has answers here:

Finding the total number of set-bits from 1 to n (17 answers)

Closed 9 years ago.

我看到一部用于计算所有单位(0,a)的1比数的代码。

int count(int a)
{
    int sum = 0;
    while(a)
    {
        sum +=1;
        a = a & (a-1);
    }
    return sum;
}
long solve(int a)
{
 if(a == 0) return 0 ;
 if(a % 2 == 0) return solve(a - 1) + count(a) ;
 return ((long)a + 1) / 2 + 2 * solve(a / 2) ;
}

我可以理解计票功能,但真的不能理解在解决问题时再次出现:

if (a%2 ==1)
   solve(a) = (a+1)/2 + 2* solve(a/2)

是否有任何人能够解释其含义? 感谢很多。

Answer 1

页: 1

solve(n) = sum of count(i) for 0<=i<=n

这等于:

solve(n) = sum of count(2j)+count(2j+1) for 0<=j<=X

由于count(2j+1) = ~(2j)+1和count(2j) = 点(j),你可以简化如下:

solve(n) = sum of 2*count(2j)+1 for 0<=j<=X
         = sum of 2*count(j)+1 for 0<=j<=X
         = 2*(sum of count(j) for 0<=j<=X) + (sum of 1 for 0<=j<=X)
         = 2*solve(X) + X + 1
         = 2*solve(floor(n/2)) + (n+1)/2

这正是你再次出现的关系。

如果n 甚至(因此不是2X+1) ,你可使用该公式。

solve(n) = count(n) + solve(n-1)

直接参照以上“<代码> 索尔ve的定义。

友情链接