Number of bits in a particular integer
When I think of bit twiddling, I think of C. So I was surprised to read Paul Khuong saying he thinks of Common Lisp (CL").
As always when working with bits, I first doodled in SLIME/SBCL: CL's bit manipulation functions are more expressive than C's, and a REPL helps exploration.
I would not have thought of Common Lisp being more expressive for bit manipulation than C, though in hindsight perhaps I should have. Common Lisp is a huge language, and a lot of thought went into it. It's a good bet that if CL supports something it supports it well.
One of the functions Khoung uses is integer-length. I looked it up in Guy Steele's book. Here's what he says about the function.
This function performs the computation
ceiling(log2(if integer < 0 then - integer else integer + 1))
... if integer is non-negative, then its value can be represented in unsigned binary form in a field whose width is no smaller than (integer-length integer). ...
Steele also describes how the function works for negative arguments and why this is useful. I've cut these parts out because they're not my focus here.
I was curious how you'd implement integer-length in C, and so I turned to Hacker's Delight. This book doesn't directly implement a counterpart to integer-length, but it does implement the function nlz (number of leading zeros), and in fact implements it many times. Hacker's Delight points out that for a 32-bit unsigned integer x,
log2(x) = 31 - nlz(x)
and
log2(x) = 32 - nlz(x -1).
So nlz(x) corresponds to 32 - (integer-length x).
Hacker's Delight implements nlz at least 10 times. I say at least" because it's unclear whether a variation of sample code discussed in commentary remarks counts as a separate implementation.
Why so many implementations? Typically when you're doing bit manipulation, you're concerned about efficiency. Hacker's Delight gives a variety of implementations, each of which may have advantages in different hardware. For example, one implementation is recommended in the case that your environment has a microcode implementation of popcount. The book also gives ways to compute nlz that involve casting an integer to a floating point number. The advisability of such a technique will be platform-dependent.
If you're looking for C implementations of integer-length you can find a few on Sean Anderson's Bit Twiddling Hacks page.
Related postsThe post Number of bits in a particular integer first appeared on John D. Cook.