El número de unidades en una representación binaria de un entero.

Question

¿Hay alguna relación que indique si el número de unos en una representación binaria de un número entero es un número par o impar?

Answer 1

Si usted está tratando de hacer esto en un ordenador, puede utilizar algunos de los algoritmos inteligentes aquí.

Answer 2

Usted podría tomar $$f(x) = (-1)^{\displaystyle \sum_{j=0}^{\lfloor \log_2(x) \rfloor} \lfloor x/2^j \rfloor}$$ for positive integers $x$. Then $f(x) = -1 $ if the number of ones is odd, $1$ si es par.

Answer 3

Llame a $p(n)$ la paridad en el número de 1's en la representación binaria de $n$ es decir $p(n) = 0$ si es o $p(n)=1$ si es impar. A continuación, si usted representa a su entero en base $B=2^{32}$ (o $2^{64}$ dependiendo del tamaño de palabra de su equipo) como $$ a_k B^k + a_{k-1}B^{k-1} + \dots + a_0 $$ a continuación, $p(n)$ es igual a $p(b)$ donde $$ b=a_k \wedge a_{k-1} \wedge \dots \wedge a_0 $$ donde $\wedge$ es sinónimo de bit a bit or exclusiva. Ahora usted puede utilizar el mismo principio para calcular $$ \begin{align}b' &= b/2^{16} \wedge (b\,\mathrm{mod} \,2^{16}),\\ b'' &= b''/2^{8} \wedge (b''\,\mathrm{mod} \,2^{8}),\\ & \dots \\ b^{(5} &= b^{(4}/2^{1} \wedge (b^{(4}\,\mathrm{mod} \,2^{1}) \end{align}$$ y $p(n) = p(b) = \dots = p(b^{(5})$ así que usted puede encontrar $p(n)$ $k+4$ 32 bits xors. Tenga en cuenta que esto no es mejor que Robert la respuesta israelí desde el punto de vista de la complejidad, pero es probablemente la más eficiente.