6
$\begingroup$

I wonder how to build efficient arithmetic network (using logical gates only) to compute floor of binary logarithm of the given input number. I have read some articles on stackoverflow.com about this problem, respectively its implementation in C/C++ using bitwise operations only.

Stackoverflow: Computing the floor of log_2(x) using only bitwise operators in C
Stackoverflow: Computing the floor log of a binary number
Bit Twiddling Hacks

I am pretty sure there's a simpler way to get this done. Using De Bruijn sequences seems to be a magic for me.

$\endgroup$
9
$\begingroup$

It can be done with a fairly simple log-depth circuit without resorting to such hacks that only really make sense in software.

The "position of most significant set bit" function pmsb can be defined recursively:

$\begin{split}pmsb(``0") &= Nil \\ pmsb(``1") &= Nil \\ pmsb(a:b) &= ``0":pmsb(b) \text{ if a=0}\\ &= ``1":pmsb(a) \text{ otherwise} \end{split}$

Where : divides a power-of-two string down the middle or concatenates two strings, depending on its context.

This can already be implemented as a circuit, but it includes some annoying wide comparisons. They can be removed by returning a tuple with an extra bit that tracks the zero-ness of the whole string (it is applied to the halves so you get the result from the halves in the recursion):

$\begin{split}pmsb(``0") &= (Nil, T) \\ pmsb(``1") &= (Nil, F) \\ pmsb(a:b) &= \text{let } (pa, za) = pmsb(a) \\ &\phantom{=}\quad\quad (pb, zb) = pmsb(b) \\ &\phantom{=}\;\; \text{in if } za \text{ then } (``0":pb, zb)\\ &\phantom{=}\quad\quad\quad\quad\text{else } (``1":pa, F) \end{split}$

This can then be evaluated bottom-up by a circuit of depth O(log n) and size O(n) where n is the length of the bit-string at the top level, which must be a power of two and not one. The zeroness bit circuit has the structure of an AND-reduction, but it is used at the intermediate nodes instead of only at the end. The main result is computed by a similar tree of MUXes that take those bits as control input.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How to interpret the result of pmsb? For 00101100 I get 1010, using the first version. $\endgroup$ – IllidanS4 wants Monica back Nov 28 '17 at 23:00
  • $\begingroup$ @IllidanS4 drop the bottom bit, but I agree this is a problem. E: fun fact, it did say Nil in my original code. I guess I got fooled by the length=1 case. $\endgroup$ – harold Nov 28 '17 at 23:18
5
$\begingroup$

The floor of the binary logarithm of $n$ is the integer $i$ such that $2^i \leq x < 2^{i+1}$. This is also the leftmost (most significant) 1 in the binary expansion of $x$. If $x = x_{n-1} \ldots x_0$, then the answer is $i$ if $x_{n-1} = \cdots = x_{i+1} = 0$ and $x_i = 1$. This leads to a simple circuit that computes $i$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.