Messages in this thread | | | Subject | Re: [patch] arca-vm-2.2.5 | From | (Eric W. Biederman) | Date | 09 Apr 1999 10:40:07 -0500 |
| |
>>>>> "GP" == Gabriel Paubert <paubert@iram.es> writes:
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/
| |