> AS> typo there, I guess. the >> should be an integer division. Since the divisor is
> AS> a constant power of 2, the compiler will optimize it into a shift.
>
> Actually I believe:
> #define DIVISOR(x) (x & ~((x >> 1) | ~(x >> 1)))
^^^^^^^^^^^^^^^^^^^^^^^
interesting formula. Unless I'm wrong, set y=x>>1 and evaluate it again:
~(y | ~y)
which should give zero on any binary machine. So I think you've come up
with a sophisticated way of generating an OOPS :-) at least on
architectures which don't silently and happily divide by zero.
I've needed it quite often but I don't know of any short formula which
computes the log2 of an integer (whether rounded up or down does not
matter) with standard C operators.
I've been looking for it quite carefully, and I don't even think that it
is possible: there is an example on how to do this in the HP-UX assembler
documentation, it takes 18 machine instructions (no loops, performing a
binary search) and it has been written by people who, as you would
expect, know very well the tricks of the architecture (cascaded
conditional nullification to perform branchless if then else: the then
branch is a shift, the else branch is an add).
Code size or time are not the problem here since it is a compile time
constant, but trying to find a simple C expression to approximate log2 is
probably futile (and not worth the effort in this case).
Gabriel.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/