ECCC-Report TR05-049https://eccc.weizmann.ac.il/report/2005/049Comments and Revisions published for TR05-049en-usTue, 26 Apr 2005 01:28:17 +0300
Paper TR05-049
| The Exact Multiplicative Complexity of the Hamming Weight Function |
Joan Boyar,
rene peralta
https://eccc.weizmann.ac.il/report/2005/049We consider the problem of computing the Hamming weight of an n-bit vector using a circuit with gates for GF2 addition and multiplication only. We show the number of multiplications necessary and sufficient to build such a circuit is n - |n| where |n| is the Hamming weight of the binary representation of n.
Tue, 26 Apr 2005 01:28:17 +0300https://eccc.weizmann.ac.il/report/2005/049