Beyond De Bruijn: fast binary logarithm of a 10-bit number

Recently I needed a method for retrieving the binary logarithm of a 10-bit number (for the curious, it was for the purpose of converting between 32-bit and 16-bit 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 two-step method where first all lower bits are set to 1 and then a De Bruijn-like 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.


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 10-bit, 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 of 0x1ff.
  • For values of v with a highest order bit at 10th position, one of 0x3fc, 0x3fd or 0x3fe could be obtained instead of 0x3ff.

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!


It is possible for multiply-and-shift 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 32-bit multiplication.

The code used for this article is included in the attached file.

  • Posted: 2012-04-03 23:15 (Updated: 2012-04-04 10:35)
  • Author: sam
  • Categories: optim c code c++

Attachments (1)

Download all attachments as: .zip


1. anonymous -- 2012-05-26 05:30

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.

2. sam -- 2012-05-27 13:32

@anonymous: Yes, you are right. I hope you will agree to the pedagogical value of the example nonetheless.

3. jilles -- 2012-11-11 16:59

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.

325. subanal -- 2016-11-27 07:00

iUQr2d Thank you, I ave been seeking for details about this subject for ages and yours is the best I ave found so far.

394. XRumerTest -- 2017-04-01 14:51

Hello. And Bye.

398. XRumerTest -- 2017-05-08 04:44

Hello. And Bye.

399. lucy ann -- 2017-05-09 15:32

NYZj6K Really informative blog article. Really Cool.

400. Jessica Barden -- 2017-11-13 14:27

I am doing a lengthy research on binary logarithm via "UK Essay Help": Your write up helped me in gathering information.

401. anonymous -- 2017-11-28 07:33

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:

402. anonymous -- 2017-11-28 12:26

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 most people excited to join the free firefox download online you upgrade your old browser and have the best browsing.

403. anonymous -- 2018-01-13 06:38

<a href="">test</a>

404. Mike -- 2018-01-13 06:42

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

405. Ramon -- 2018-01-13 08:11

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

406. Andre -- 2018-02-05 21:37

I almost went crazy with so many numbers, but I understood the explanation hahaha

407. Amanda Johnson -- 2018-03-03 02:34

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

408. anonymous -- 2018-03-20 13:34

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. C9060-528

409. R Programming Assignment Assistance -- 2018-03-26 12:49

I personally like your post, you have shared good article. It will help me in great deal. <a href="">R Programming Assignment Assistance</a>

410. Statistics Homework Help -- 2018-03-26 12:50

This is really great work. Thank you for sharing such a useful information here in the blog. <a href="">Statistics Homework Help</a>

411. Operations Research Assignments help -- 2018-03-26 13:45

This was a great and interesting article to read. I have really enjoyed all of this very cool information

412. Sociology Assignment Help -- 2018-03-26 13:46

My friend recommended this blog and he was totally right keep up the good work

413. anonymous -- 2018-05-10 20:26

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.

414. Scott Stevens -- 2018-05-17 11:18

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="">Cheap Essay Writing Service UK</a>

Add New Comment