An official website of the United States government
Here’s how you know
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
The Exact Multiplicative Complexity of the Hamming Weight Function
Published
Author(s)
Rene C. Peralta, Joan Boyar
Abstract
We consider the problem of computing the Hamming weight of an n-bit vector using a circuit with gates for addition and multiplication modulo 2 (alternatively, XOR and conjunction gates) only. The number of multiplications necessary and sufficient to build such a circuit is called the multiplicative complexity of the Hamming weight function. We prove the exact multiplicative complexity of the Hamming weight function on n variables is n minus the Hamming weight of the binary representation of n.
Peralta, R.
and Boyar, J.
(2005),
The Exact Multiplicative Complexity of the Hamming Weight Function, Proceedings published by Springer-Verlag
(Accessed June 7, 2023)