__
TR05-049 | 1st April 2005 00:00
__

#### The Exact Multiplicative Complexity of the Hamming Weight Function

**Abstract:**
We 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.