GP> On 9 Apr 1999, Eric W. Biederman wrote:
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)))
GP> ^^^^^^^^^^^^^^^^^^^^^^^
GP> interesting formula. Unless I'm wrong, set y=x>>1 and evaluate it again:
GP> ~(y | ~y)
GP> which should give zero on any binary machine.
Duh. I forgot that the high bits got set.
GP> So I think you've come up
GP> with a sophisticated way of generating an OOPS :-) at least on
GP> architectures which don't silently and happily divide by zero.
GP> I've needed it quite often but I don't know of any short formula which
GP> computes the log2 of an integer (whether rounded up or down does not
GP> matter) with standard C operators.
Well I wasn't trying for log2 but instead for truncating to the nearest
power of two, in a form that the compiler could compute, at compile time.
GP> I've been looking for it quite carefully, and I don't even think that it
GP> is possible: there is an example on how to do this in the HP-UX assembler
GP> documentation, it takes 18 machine instructions (no loops, performing a
GP> binary search) and it has been written by people who, as you would
GP> expect, know very well the tricks of the architecture (cascaded
GP> conditional nullification to perform branchless if then else: the then
GP> branch is a shift, the else branch is an add).
GP> Code size or time are not the problem here since it is a compile time
GP> constant, but trying to find a simple C expression to approximate log2 is
GP> probably futile (and not worth the effort in this case).
True but it is fun :)
Eric
-
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/