Beyond De Bruijn: fast binary logarithm of a 10bit number
Recently I needed a method for retrieving the binary logarithm of a 10bit number (for the curious, it was for the purpose of converting between 32bit and 16bit floating point numbers).
Computing the binary logarithm is equivalent to knowing the position of the highest order set bit. For instance, log2(0x1)
is 0 and log2(0x100)
is 8.
One well known method for fast binary logarithm is presented at Bit Twiddling Hacks. It is a twostep method where first all lower bits are set to 1 and then a De Bruijnlike sequence is used to perform a table lookup:
int fastlog2(uint32_t v) { static const int MultiplyDeBruijnBitPosition[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; v = v >> 1; v = v >> 2; v = v >> 4; v = v >> 8; v = v >> 16; return MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27]; }
That is 12 integer operations and a table lookup.
Optimising
It should be obvious what the sequence of operations on v
does: fill the integer with ones starting from the highest order bit. Here are a few examples of what happens to v
at each step:
v  v = v >> 1  v = v >> 2  v = v >> 4  v = v >> 8  v = v >> 16

0x0001  0x0001  0x0001  0x0001  0x0001  0x0001 
0x0002  0x0003  0x0003  0x0003  0x0003  0x0003 
0x0003  0x0003  0x0003  0x0003  0x0003  0x0003 
0x0004  0x0006  0x0007  0x0007  0x0007  0x0007 
0x0100  0x0180  0x01e0  0x01fe  0x01ff  0x01ff 
0x80000000  0xc0000000  0xf0000000  0xff000000  0xffff0000  0xffffffff 
There is one obvious optimisation available: since the input is only 10bit, the last shift operation v = v >> 16
can be omitted because the final value was already reached.
int fastlog2(uint32_t v) { static const int MultiplyDeBruijnBitPosition[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 }; v = v >> 1; v = v >> 2; v = v >> 4; v = v >> 8; return MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27]; }
10 instructions instead of 12. Not really amazing, but worth mentioning.
Optimising more?
Could we do better? Now the last line is v = v >> 8;
and it is only useful to propagate the 9th and 10th bits to positions 1 and 2. What happens if we omit that line? Let’s see:
 For most values of
v
, the expected value is obtained.  For values of
v
with a highest order bit at 9th position,0x1fe
could be obtained instead of0x1ff
.  For values of
v
with a highest order bit at 10th position, one of0x3fc
,0x3fd
or0x3fe
could be obtained instead of0x3ff
.
The list of possible output values would therefore be 0x1
, 0x3
, 0x7
, 0xf
, 0x1f
, 0x3f
, 0x7f
, 0xff
, 0x1fe
, 0x1ff
, 0x3fc
, 0x3fd
, 0x3fe
, 0x3ff
. What happens to these values when multiplying them with the De Bruijn sequence? Let's see:
v  v * 0x07C4ACDDU) >> 27

0x1  0 
0x3  2 
0x7  6 
0xf  14 
0x1f  30 
0x3f  29 
0x7f  27 
0xff  23 
0x1fe  15 
0x1ff  16 
0x3fc  30 
0x3fd  31 
0x3fe  0 
0x3ff  1 
Damn! Two values are colliding. It looks like we cannot omit the last line after all.
Beyond De Bruijn
Let’s give another try at the problem. Usually De Bruijn sequences are built using either nontrivial algorithms, or brute force. Maybe we could find another sequence that has no collision? Or a sequence that is not a De Bruijn sequence but that works for our problem?
Well, let’s just brute force!
(2 seconds later)
int fastlog2(uint32_t v) { static const int MagicTable[16] = { 0, 1, 2, 8, 1, 3, 5, 9, 9, 7, 4, 1, 6, 1, 1, 1 }; v = v >> 1; v = v >> 2; v = v >> 4; return MagicTable[(uint32_t)(v * 0x5a1a1a2u) >> 28]; }
Down to 8 instructions instead of 12. And the lookup table is now half the size!
Conclusion
It is possible for multiplyandshift techniques similar to the De Bruijn sequence algorithm to exist for a larger set of problems. Brute forcing the search is a totally valid method for 32bit multiplication.
The code used for this article is included in the attached file.
Attachments (1)
 debruijn.cpp (2.1 KB)  added by 6 years ago.
Download all attachments as: .zip
Comments
Not to spoil the fun, but bsr can do what you are doing much faster. GCC even has a builtin for it namely, builtin_clz.
@anonymous: Yes, you are right. I hope you will agree to the pedagogical value of the example nonetheless.
Actually, on Intel Atom and AMD K8, BSR is very slow and the example may be faster in inner loops. However, even on such processors, BSR may be better because less cache space (instruction as well as data) is used.
iUQr2d Thank you, I ave been seeking for details about this subject for ages and yours is the best I ave found so far.
Hello. And Bye.
Hello. And Bye.
NYZj6K Really informative blog article. Really Cool.
I am doing a lengthy research on binary logarithm via "UK Essay Help":https://www.writingbunch.co.uk Your write up helped me in gathering information.
We should give another attempt to the issue. As a rule, De Bruijn successions are constructed utilizing either nontrivial calculations or savage power. Possibly we could discover another arrangement that has no impact? Or, on the other hand, a succession that isn't a De Bruijn grouping however that works for our concern?
Web Source: https://www.groovyessays.co.uk/
You join the latest free online mozilla firefox free download latest version and i sure you create the best speed to downloading just click here https://foxdownload.org most people excited to join the free firefox download online you upgrade your old browser and have the best browsing.
<a href="https://www.test.com">test</a>
I have read the post, you have posted very nice tutorial which i like reading. I have got information which i did not know before. I will come back to read more similar articles. Buy sticker roll http://www.rollstickersco.com/
This is a great educational post. I am impressed to see the article you have posted really found it very good to read. I have learned a lot which i did not know before. Buy sticker printing from http://www.astickerprinting.co.uk/
I almost went crazy with so many numbers, but I understood the explanation hahaha https://futeboltrading.com/betmotion/
You should check different traps to register the log2 and consider utilizing the MSR get together direction on the off chance that you are on x86(_64). It gives you the record of the most noteworthy set piece, which is precisely what you require.
UK Dissertation Help
What a amazing post shared here. I really love this website, I would like to say thanks for sharing such great post. I would like to say bundle of thanks for sharing. C9060528
I personally like your post, you have shared good article. It will help me in great deal. <a href="https://rprogramminghelp.xyz/">R Programming Assignment Assistance</a>
This is really great work. Thank you for sharing such a useful information here in the blog. <a href="https://statisticshelponline.xyz/">Statistics Homework Help</a>
This was a great and interesting article to read. I have really enjoyed all of this very cool information http://www.theoperationsmanagement.com/operationsresearch3147
My friend recommended this blog and he was totally right keep up the good work http://www.sociologyassignments.com/
I am really poor in mathematics but, after started following your website I learned a lot about math subject. The tricks which you have posted in custom writing service reviews blog have made me to visit your blog. After visiting your blog I came to know the beauty of this subject and learned tricks to solving problems.
This is an extraordinary instructive post. I am awed to see the article you have posted extremely thought that it was great to peruse. I have taken in a great deal which I didn't know previously.<a href="https://www.writemyessays.org.uk/essaywritingservice.php">Cheap Essay Writing Service UK</a>
Excellent article. Very interesting to read. I really love to read such a nice article. https://arynews.tv/en/category/pakistanelections2018/
If you had been hoping for an elegant mathematical formulation to describe them or theorem to provide them or something comparable, I suppose this would require profound insight into range concept and possibly different fields that are beyond my skillset. If I wherein to make a wild wager I would guess they may be produced by means of cellular automata. This isn't always an answer why? On a rigorous base, however, an attempt to intuitively recognize why it really works and why it works nicely so that you can use it with selfbelief. Essay Writing Service UK
Students often feel issues in writing assignment, so to make students comfortable in java assignment we help them to write their assignments. If ever you feel any problem in writing something you can visit our website Java Assignment Help.If you want help in writing assignment than contact our experts. https://www.allassignmenthelp.com/javaassignmenthelp.html
Fantastic blog! Do you have any tips and hints for aspiring writers? I’m planning to start my own website soon but I’m a little lost on everything. Would you propose starting with a free platform like WordPress or go for a paid option? There are so many options out there that I’m completely overwhelmed .. Any suggestions? Many thanks! como conquistar o ex http://casamentorestaurado.info/
I've had a mental obstacle for a decent 5 years and this was the principal thing that started my imagination in, well, five years lol. I quit composing 500 pages into a novel (that will require a considerable measure of altering lol) that is a piece of a set of three I have sketched out in detail. Actually the peak of the book, and I just.... couldn't continue onward. I compose a considerable measure for school/work yet not in an inventive sense. https://www.freshessays.co.uk/
Impressive web site, Distinguished feedback that I can tackle. I am moving forward and may apply to my current job as a pet sitter, which is very enjoyable, but I need to additional expand. Regards. crossbowarticles.com
Impressive web site, Distinguished feedback that I can tackle. I am moving forward and may apply to my current job as a pet sitter, which is very enjoyable, but I need to additional expand. Regards. <a href='http://www.crossbowarticles.com'>crossbowarticles.com</a>
Impressive web site, Distinguished feedback that I can tackle. I am moving forward and may apply to my current job as a pet sitter, which is very enjoyable, but I need to additional expand. Regards. crossbowarticles.com http://www.crossbowarticles.com
This is really a nice and informative, containing all information and also has a great impact on the new technology. Thanks for sharing it <a href='http://www.subicevac.com'>Subi Cevac</a>
This is really a nice and informative, containing all information and also has a great impact on the new technology. Thanks for sharing it Subi Cevac http://www.subicevac.com
I have bookmarked your blog, the articles are way better than other similar blogs.. thanks for a great blog! <a href='https://www.youtube.com/watch?v=imiGL2YS2uo'>a course in miracles</a>
SuperDuper site! I am Loving it!! Will come back again, Im taking your feed also, Thanks. a course in miracles https://acimonlinevideo.net/
The information you have posted is very useful. The sites you have referred was good. Thanks for sharing.. https://acimcentre.org/ https://acimcentre.org/
I would like to say that this blog really convinced me to do it! Thanks, very good post. <a href='https://www.youtube.com/channel/UCP9Gw00CldPUmiu43y7fdWw'>ucdm</a>
Custom Deluxe Boxes specialize in designing custom product boxes of all styles, sizes and materials. We are known as the manufactures of best custom product boxes in USA and Canada. Our team has gained extensive experience by working for different manufacturers, companies and brands. We have helped thousands of our clients to be successful by giving the right look to their product packaging. https://www.dukepackaging.com/
Thanks for this great post, i find it very interesting and very well thought out and put together. I look forward to reading your work in the future. click this http://www.narutocrisis.com
The information you have posted is very useful. The sites you have referred was good. Thanks for sharing... <a href='http://www.hepburnandhemingway.com/'>browse this site</a>
Thank you for some other informative blog. Where else could I get that type of information written in such an ideal means? I have a mission that I’m just now working on, and I have been at the look out for such information. discover here http://www.annusit.com/
Wonderful article, thanks for putting this together! This is obviously one great post. Thanks for the valuable information and insights you have so provided here. Lebensversicherung auflösen https://hasso24.de/
useful information on topics that plenty are interested on for this wonderful post.Admiring the time and effort you put into your b!.. Mon Bazar http://www.monbazar.ca
That is the excellent mindset, nonetheless is just not help to make every sence whatsoever preaching about that mather. Virtually any method many thanks in addition to i had endeavor to promote your own article in to delicius nevertheless it is apparently a dilemma using your information sites can you please recheck the idea. thanks once more. Ottawa Distribution Services http://www.ottawadistributionservices.ca
You know your projects stand out of the herd. There is something special about them. It seems to me all of them are really brilliant! Sharrard Law http://www.sharrardlaw.com
All the contents you mentioned in post is too good and can be very useful. I will keep it in mind, thanks for sharing the information keep updating, looking forward for more posts.Thanks a course in miracles https://acourseinmiraclesnow.com/
You have done a great job on this article. It’s very readable and highly intelligent. You have even managed to make it understandable and easy to read. You have some real writing talent. Thank you. a course in miracles https://miracleshome.org/
I’ve been searching for some decent stuff on the subject and haven't had any luck up until this point, You just got a new biggest fan!.. Primeworld District Lapu Lapu http://primeworlddistrict.com/
To score good marks in their college and university, they can avail our excellent services. Our assignment experts can write complicated <a href="https://www.makemyassignments.com/">Online Assignment Help</a> as they are wellversed with every academic topic.
I am hoping the same best effort from you in the future as well. In fact your creative writing skills has inspired me. Transfer Super 8 Film to DVD https://sflmediatransfer.com
If students are getting knowledge in the Singaporean university and want to get a higher score in your assignment then worry no more, come at StudentsAssignmentHelp.com and take our Assignment Help Singapore services.
Check Here: https://www.studentsassignmenthelp.com/sg/