<commit_before>---
title: 'Popcount / Hamming weight (# bit set)'
published: true
tags: c++ bits lookup hamming
---
> Population count is a procedure of counting number of ones in a bit string. - [The NSA Instruction](https://vaibhavsagar.com/blog/2019/09/08/popcount/) / [HN](https://news.ycombinator.com/item?id=20914479)

- [Generating Binary Permutations in Popcount Order](https://alexbowe.com/popcount-permutations/)
- [Bit Hacks](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2018/lecture-slides/MIT6_172F18_lec3.pdf) 

## [std::popcount](https://en.cppreference.com/w/cpp/numeric/popcount)

{% highlight cpp %}
#include <bit>
std::popcount(i)
{% endhighlight %}

## Using the built-in functions of your compilers.
For GCC:
{% highlight cpp %}
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x)
{% endhighlight %}

## [SSSE3: fast popcount](http://0x80.pl/articles/sse-popcount.html)

SSSE3 has powerful instruction PSHUFB. This instruction can be used to perform a parallel 16-way lookup; LUT has 16 entries and is stored in an XMM register, indexes are 4 lower bits of each byte stored in another XMM register.

Depending on architecture i5 (Westmere) vector can be slower or much faster  Core i7 (Haswell) Core i7 (Skylake) for a sufficiently long bitstring (> 128 bytes).

## [Hamming Weight](https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer/109025#109025)

GCC and clang 10.0 can recognize this pattern / idiom and [compile it to a hardware popcnt](https://godbolt.org/z/qGdh1dvKK) or equivalent instruction when available, giving you the best of both worlds. 
  
{% highlight cpp %}
int popcount(uint32_t i) {
     i = i - ((i >> 1) & 0x55555555);        // add pairs of bits
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // quads
     i = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8
     return (i * 0x01010101) >> 24;          // horizontal sum of bytes
}
{% endhighlight %}<commit_msg>Update 2018-07-11-bit-count-set.md<commit_after>---
title: 'Popcount / Hamming weight (# bit set)'
published: true
tags: c++ bits lookup hamming
---
> Population count is a procedure of counting number of ones in a bit string. - [The NSA Instruction](https://vaibhavsagar.com/blog/2019/09/08/popcount/) / [HN](https://news.ycombinator.com/item?id=20914479)

- [Generating Binary Permutations in Popcount Order](https://alexbowe.com/popcount-permutations/)
- [Bit Hacks](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2018/lecture-slides/MIT6_172F18_lec3.pdf) 

## [std::popcount](https://en.cppreference.com/w/cpp/numeric/popcount)

{% highlight cpp %}
#include <bit>
std::popcount(i)
{% endhighlight %}

## Using the built-in functions of your compilers.
For GCC:
{% highlight cpp %}
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x)
{% endhighlight %}

## [SSSE3: fast popcount](http://0x80.pl/articles/sse-popcount.html)

SSSE3 has powerful instruction PSHUFB. This instruction can be used to perform a parallel 16-way lookup; LUT has 16 entries and is stored in an XMM register, indexes are 4 lower bits of each byte stored in another XMM register.

Depending on architecture i5 (Westmere) vector can be slower or much faster  Core i7 (Haswell) Core i7 (Skylake) for a sufficiently long bitstring (> 128 bytes).

## [Hamming Weight](https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer/109025#109025)

GCC and clang 10.0 can recognize this pattern / idiom and [compile it to a hardware popcnt](https://godbolt.org/z/qGdh1dvKK) or equivalent instruction when available, giving you the best of both worlds. 

The best method for counting bits in a 32-bit integer v [is the following](https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel): 
  
{% highlight cpp %}
int popcount(uint32_t i) {
     i = i - ((i >> 1) & 0x55555555);        // add pairs of bits
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // quads
     i = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8
     return (i * 0x01010101) >> 24;          // horizontal sum of bytes
}
{% endhighlight %}
{'fraction_non_alphanumeric': 0.1298342541436464, 'fraction_numerical': 0.05755064456721915, 'mean_word_length': 3.94874715261959, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 25, 'https://': 15, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 6, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '227472', 'n_tokens_mistral': 1655, 'n_tokens_neox': 1415, 'n_words': 427}