Dado un valor$N$, necesito encontrar$\sum_{i=1}^N i X_i$ donde$X_i$ es el número de 1 bits en la representación binaria de$i$. Intenté encontrar los valores hasta un poder particular de 2 y resumirlo. Por ejemplo, la representación binaria de$N=6$ es$110$. Podemos almacenar valor hasta 4, y valor hasta 2, así, y utilizar alguna manipulación sobre estos 2 valores para obtener la respuesta de 6. Pero, de alguna manera soy incapaz de obtener la relación.
Respuesta
¿Demasiados anuncios?
marty cohen
Puntos
33863
Aquí es un comienzo para obtener la suma hasta el $2^n$.
Vamos $s(N) = \sum_{i=1}^N i X_i $ y $t(N) = \sum_{i=1}^N X_i $.
Voy a tener recurrencias para $t(2^n)$ y $s(2^n)$ a partir de la cual se puede obtener fórmulas para ellos.
Voy a dejar en este porque soy perezoso.
$\begin{array}\\ t(2^{n+1}) &= \sum_{i=1}^{2^{n+1}} X_i\\ &= \sum_{i=1}^{2^{n}} X_i+\sum_{i=2^n+1}^{2^{n+1}} X_i\\ &= t(2^n)+\sum_{i=1}^{2^{n}} X_{2^n+i}\\ &= t(2^n)+\sum_{i=1}^{2^{n}} (1+X_{i})\\ &= t(2^n)+\sum_{i=1}^{2^{n}} 1+\sum_{i=1}^{2^{n}} X_{i}\\ &= 2t(2^n)+2^n\\ \end{array} $
Dejar $t(2^n) = T(n)$, esto se convierte en $T(n+1) =2T(n)+2^n $. Dividiendo por $2^{n+1}$, $\dfrac{T(n+1)}{2^{n+1}} =\dfrac{T(n)}{2^n}+\dfrac12 $.
$\begin{array}\\ s(2^{n+1}) &= \sum_{i=1}^{2^{n+1}} i X_i\\ &= \sum_{i=1}^{2^{n}} i X_i+\sum_{i=2^n+1}^{2^{n+1}} i X_i\\ &= \sum_{i=1}^{2^{n}} i X_i+\sum_{i=1}^{2^{n}} (2^n+i) X_{2^n+i}\\ &= \sum_{i=1}^{2^{n}} i X_i+\sum_{i=1}^{2^{n}} (2^n+i) (1+X_{i})\\ &= \sum_{i=1}^{2^{n}} i X_i+\sum_{i=1}^{2^{n}} (2^n+i) +\sum_{i=1}^{2^{n}} (2^n+i) X_{i}\\ &= 2\sum_{i=1}^{2^{n}} i X_i+\sum_{i=1}^{2^{n}} (2^n+i) +2^n\sum_{i=1}^{2^{n}} X_{i}\\ &= 2s(2^n)+2^{n+1}+2^n(2^n+1)/2+2^nt(2^n)\\ &= 2s(2^n)+2^{n+1}+2^{n-1}+2^{2n-1}+2^nt(2^n)\\ &= 2s(2^n)+2^{n-1}(2^n+5)+2^nt(2^n)\\ \end{array} $
Dejar $s(2^n)=S(n)$, esto se convierte en $S(n+1) =2S(n)+\frac12 2^n(2^n+5)+2^nT(n) $. Dividiendo por $2^{n+1}$, esto se convierte en $\dfrac{S(n+1)}{2^{n+1}} =\dfrac{S(n)}{2^n}+\frac14 (2^n+5)+\frac12 T(n) $.
