4

Given an unsigned number, what is a good (preferably fast) way of getting the number of leading 1-bits?

I need this to calculate the CIDR number from a quad-dotted IPv4 netmask.

Note: I have seen getting-the-number-of-trailing-1-bits, so I can do the table-based lookup.

Note 2: Even though I added a couple of language tags, for me it is about the algorithm, so if you have a good one in another language, please feel free to post.

Edit: on endian-ness.

I just found out that the INET_ADDR function and IN_ADDR structure store the IPv4 address in big-endian form, whereas the x86 is little-endian, and most of the processors I use are little-endian too.
So, lookup tables for this specific case are fast enough.
But thanks for the other answers: they work very nicely in the more common case.

--jeroen

Community
  • 1
  • 1
Jeroen Wiert Pluimers
  • 23,965
  • 9
  • 74
  • 154

4 Answers4

12

If you invert all the bits, you can use a leading-one detection algorithm (equivalent to a log2 algorithm); see e.g. http://www-graphics.stanford.edu/~seander/bithacks.html. You may be able to modify some of those algorithms, and skip the inversion stage.

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
5

If all the bits are 0 before the 1s you can use the BSF assembler instruction, it will return the index of the first bit set (not zero) starting from the lower bit, then you can subtract it from 32 and obtain the number of bits set.
Otherwise if you have to look for from the high bit you can use NOT to invert the bits, and the use BSR to scan from the high bit to zero.

Jeroen Wiert Pluimers
  • 23,965
  • 9
  • 74
  • 154
  • 1
    Though I'd asked for the algorithm, it is good to know there is an x86 assembly solution too. I'll edit your answer with some links as other people might be interested in them too. – Jeroen Wiert Pluimers Jan 17 '11 at 14:02
  • 1
    Note: These are also sometimes known as "CTZ/CLZ" (count leading/trailing zeros). – SoapBox Jan 17 '11 at 14:08
  • 1
    I would also suggest to refer to the Intel manual (freely downloadable from here http://www.intel.com/products/processor/manuals/) as the official reference- –  Jan 17 '11 at 19:26
5

Unless you are specifically looking for theoretical improvements in number of steps (i.e. O(lg(n)) in number of bits), I don't think you will practically do much better than table lookup and still have an algorithm that's portable.

I'd expect to comfortably scan over 100 million IPv4 netmasks for leading ones per second using a simple table lookup on a single thread on a modern machine (excluding the work of actually getting hold of the IPv4 netmask). I'm not sure the gains from further algorithmic improvement would be worth any added complexity.

Barry Kelly
  • 41,404
  • 5
  • 117
  • 189
  • +1 for making sure we keep our feet on the ground. Another reason is that the in_addr structure is not little-endian, so table lookup is easier than swapping the bytes around. – Jeroen Wiert Pluimers Jan 17 '11 at 14:04
5

This question, though completely unrelated, shows some C code for doing CTZ/CLZ (Count Leading/Trailing Zeros). If you invert (bitwise not) your input before calling one of these you can get the number of leading/trailing ones.

Community
  • 1
  • 1
SoapBox
  • 20,457
  • 3
  • 51
  • 87