Getting the number of leading 1 bits

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

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.

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.

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.

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.