The Exact Multiplicative Complexity of the Hamming Weight Function
Joan Boyar, René Peralta · Electronic colloquium on computational complexity · 2005
AbstractWe consider the problem of computing the Hamming weight of an n-bitvector using a circuit with gates for addition and multiplication modulo 2 (al-ternatively, XOR and conjunction gates) only. The number of multiplicationsnecessary and sufficient to build such a circuit is called the “multiplicativecomplexity” of the Hamming weight function, and is denoted by c ∧ (H n ). Weprove c ∧ (H n ) = n−H N (n) where H N (n) is the Hamming weight of the binaryrepresentation of n. 1 Introduction The multiplicative complexity c ∧ (f) of a Boolean function f is the number of con-junctions necessary and sufficient to implement a circuit which computes f over thebasis (∧,⊕,1) (alternatively, the number of multiplications necessary and sufficientto calculate a function over GF 2 via a straight-line program). Let→H(x) denote the ∗ Department of Mathematics and Computer Science, University of Southern Denmark. Partiallysupported by the Future and Emerging Technologies programme of the EU under contract numberIST-1999-14186 (ALCOM-FT), and by the Danish Natural Science Research Council (SNF).