Hamming weight for vector<int> C++

Question

I'm working on a the Hamming weight for a vector and what I do is count in linear way all the 1 in the vector, is there any more efficient way?

int HammingWeight(vector<int> a){
    int HG=0;

    for(int i=0; i<a.size(); i++){
        if(a[i] == 1)
            HG++;
    }
    return HG;
}

Answer 1

To calculate the hamming weight, you need to visit each element, giving you O(n) best case, making your loop as efficient as it gets when discounting micro optimizations.

However your function call itself is extremely inefficient: You pass the vector by value, resulting in a copy of all it's content. This copy can easily be more expensive then the rest of the function combined. Furthermore there is nothing at all in your function which actually needs that copy. So changing the signature to int HammingWeight(const std::vector<int>& a) should make your function much more efficient.

Another (possible) optimization comes to mind, assuming your vector only contains ones and zeros (otherwise I don't see how your code makes sense). In that case you could just add the corresponding vectorelement to HG, getting rid of the if (addition is typically much faster then branching):

 for(size_t i=0; i<a.size(); ++i)
    HG+=a[i];

I would assume this to likely be faster, however whether or not it actually is isdepends on how the compiler optimizes.

If you'd actually need to you could of course apply common microoptimizations (loop unrolling, vectorization, ...), but that would be premature unless you have good reason to. Besides in that case the first thing to do (again assuming the vector only contains zeros and ones) would be to use a more compact (read efficient) representation of the data.

Also note that both approaches (the direct summation and the if version) could also be expressed using the standard library:

• int HG=std::count(a.begin(), a.end(), 1); does basically the same thing as your code
• int HG=std::accumulate(a.begin(), a.end(), 0); would be equivalent to the loopI mentioned above

Now this is unlikely to help performance, but using less code to archieve the same effect is typically considered a good thing.