Re: [CHALLENGE] finding rightmost zero bit - C programmer's take
- From: glen herrmannsfeldt <gah@xxxxxxxxxxxxxxxx>
- Date: Tue, 30 Aug 2005 08:25:47 -0700
N. Shamsundar wrote:
(snip)
This task seemed one that was made for C, so here are my comments from that end (I program in C and Fortran).
(snip)
1. A good C compiler can produce inline code that beats assembler code; one reason: function call overhead in using the assembler functions.
2. The heart of the program (lines 12 and 13) is simple and natural in C. (This statement is in no way meant to be derogatory to Fortran.)
(snip)
for(x=y, i=0; i<32; i++){
if(! (x & 1))break;
x=x >> 1;
}
It is slightly less simple and slightly less natural in Fortran, but not so bad. I have no idea how much optimizing either compiler does on it.
x=y
do 1 i=0,31
if(iand(x,1).eq.0) goto 2
x=ishft(x,-1)
1 continue
2 continueThe logical functions are at least as old as IBM Fortran H with the XL
option, the first Fortran compiler that I knew of that was mostly (though not completely) written in Fortran. The logical operations
were needed to compile the compiler.
Treating a 32 bit integer as four separate unsigned bytes is somewhat easier in C, though doing it completely according to the standard isn't so easy. That allows speeding up some table lookup algorithms on some machines.
If implemented with conditional load and for uniform distribution of return values, I believe mine will be close to the fastest. For uniform distribution of input values the quick exit unrolled loop should be fastest. All are fairly sensitive to branch timings, the limiting factor on many current processors.
-- glen
.
- Follow-Ups:
- Re: [CHALLENGE] finding rightmost zero bit - C programmer's take
- From: Dr Ivan D. Reid
- Re: [CHALLENGE] finding rightmost zero bit - C programmer's take
- References:
- [CHALLENGE] finding rightmost zero bit
- From: Bart Vandewoestyne
- Re: [CHALLENGE] finding rightmost zero bit - C programmer's take
- From: N. Shamsundar
- [CHALLENGE] finding rightmost zero bit
- Prev by Date: Re: Algorithm for "1st Tuesday", "last Saturday", etc.
- Next by Date: Re: [CHALLENGE] finding rightmost zero bit - C programmer's take
- Previous by thread: Re: [CHALLENGE] finding rightmost zero bit - C programmer's take
- Next by thread: Re: [CHALLENGE] finding rightmost zero bit - C programmer's take
- Index(es):
Relevant Pages
|
|
