<commit_before>---
title: Find most significant bits
published: true
tags: c++ bits
---
## [Bruijn multiplication.](https://stackoverflow.com/a/31718095/51386)
The de Bruijn version beats the other implementations soundly because it is branchless, and therefore it runs well against inputs that produce an evenly distributed set of outputs. All the other versions are slower against arbitrary inputs because of the penalties of branch misprediction on modern CPUs. The smbFfs function produces incorrect results so it can be ignored.

Here are the results in performance mode, running on my i7-4600 laptop, compiled in release mode:

{% highlight cpp %}
msbLoop64 took 2.56751 seconds               
msbNative64 took 0.222197 seconds            

msbLoop32 took 1.43456 seconds               
msbFfs took 0.525097 seconds                 
msbPerformanceJunkie32 took 1.07939 seconds  <commit_msg>Update 2018-07-02-bit-msb.md<commit_after>---
title: Find most significant bits (msb)
published: true
tags: c++ bits
---
- [__builtin_ctz](https://www.geeksforgeeks.org/builtin-functions-gcc-compiler/) = Number of trailing zero's, but require value to be non-zero.

## [Bruijn multiplication.](https://stackoverflow.com/a/31718095/51386)
The de Bruijn version beats the other implementations soundly because it is branchless, and therefore it runs well against inputs that produce an evenly distributed set of outputs. All the other versions are slower against arbitrary inputs because of the penalties of branch misprediction on modern CPUs. The smbFfs function produces incorrect results so it can be ignored.

Here are the results in performance mode, running on my i7-4600 laptop, compiled in release mode:

{% highlight cpp %}
msbLoop64 took 2.56751 seconds               
msbNative64 took 0.222197 seconds            

msbLoop32 took 1.43456 seconds               
msbFfs took 0.525097 seconds                 
msbPerformanceJunkie32 took 1.07939 seconds  
{'fraction_non_alphanumeric': 0.05975485188968335, 'fraction_numerical': 0.06332992849846783, 'mean_word_length': 3.555813953488372, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 3, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, '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': '1048666', 'n_tokens_mistral': 607, 'n_tokens_neox': 501, 'n_words': 231}