как понять код: вычислить число 1 в диапазоне (0: а)

Я вижу код, который используется для вычисления общего количества 1-битов во всех целых числах в диапазоне (0, а).

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)

Есть ли кто-нибудь, кто может объяснить немного это? Большое спасибо.


recurrence algorithm
person xueliang liu    schedule 10.05.2012    source источник
comment
Попробуйте пошагово выполнить код в своей любимой IDE/отладчике.   -  person Paul R    schedule 10.05.2012

Ответы (1)


arrow_upward
2
arrow_downward

Предположим, у вас есть номер n = 2X+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) = count(2j)+1 и count(2j) = count(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)

что следует непосредственно из определения solve как суммы выше.

person interjay    schedule 10.05.2012