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(log_{2}(ifinteger< 0then−integerelseinteger+ 1))… if

integeris 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*,

⌊log_{2}(*x*)⌋ = 31 – `nlz`

(*x*)

and

⌈log_{2}(*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.

I am unhappy that “integer-length” for both 0 and -1 require 0 bits, but “they’re not my focus here”.

In APL “integer-length” can be simply implemented without needing the “If/then/else” branching alternatives, as a single computation:

{⌈2⍟(0⌈×⍵+1)+|⍵}

so for the integers 0 1 2 3 4 5 8 16 32 64 ¯4 ¯64 and 10 to the power 16

{⌈2⍟(0⌈×⍵+1)+|⍵} 0 1 2 3 4 5 8 16 32 64 ¯4 ¯64 , 10*16

0 1 2 2 3 3 4 5 6 7 2 6 54