NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.

Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.

U.S. flag

An official website of the United States government

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.

PUBLICATIONS

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.
Proceedings Title
Proceedings published by Springer-Verlag
Conference Dates
September 13, 2005
Conference Title
Latin American Theoretical Informatics Symposium
Pub Type
Conferences

Keywords

circuit complexity, complexity, concrete complexity, cryptographic proofs, Hamming weight, multiplicative, symmetric functions
Information technology

Citation

Peralta, R. and Boyar, J. (2005), The Exact Multiplicative Complexity of the Hamming Weight Function, Proceedings published by Springer-Verlag (Accessed October 7, 2025)

Issues

If you have any questions about this publication or are having problems accessing it, please contact [email protected].

Created September 13, 2005, Updated February 19, 2017
Was this page helpful?