i=length;while(i--)
A wonderful little device in C or C++ which is very useful. It is like your standard loop for(i=0;i<length;i++), except it does the same thing backwards. With while(i--), the loop's contents are executed i times, starting with i-1 and ending with 0. Sometimes it just doesn't matter which order you loop, or even what the value of i is during the loop. In these cases, you are able to use while(i--) to have a more efficient executable.

Why is it more efficient? Well, it only uses one variable in the loop, i, unlike the for loop, which uses i and length.

With gcc on a Pentium:

  • while(i--):
    1. decrement i
    2. test -1 with i
    3. if the result is "not equal", then execute loop contents
    4. otherwise jump out of the loop
  • for(;i<length;i++):
    1. move length into register EAX
    2. test i with EAX
    3. if the result is "less than", then execute the loop
    4. otherwise jump out of the loop
    At the end of the loop execution:
    1. increase i
With optimization enabled, the while loop actually compresses into 2 instructions, using some weird characteristics of the 80x86 processor, whereas the for loop squeezes down to 3 (also using an extra register). (An interesting note: if i is unused in the loop body, gcc will make the for loop count down as if it was while(i--))

The problems

  • Obscure - the meaning of while(i--) is not as obvious as with your standard for loop, but a programmer can get just as used to it as he first did with for.
  • Risky - if i starts out less than 0, the loop will be going way longer than we had expected... This can be solved in either of two ways:
    1. Initially check if i is less than 0.
    2. Use while(i-->=0) - probably just as efficient, but less elegant looking :-)
So, as you can see, while(i--) is quite nice. I came up with the idea, or maybe I "independently invented" it. People who like while(i--) probably also like Duff's Device.

Of course, the same thing can be done with a for loop, and use one less line of code. I like to look at for as the Swiss Army Loop.

for(i=length; i--;) 
or, if you only need to execute one statement:
for(i=length; i; f(i--)) ;
The idea itself has been widely used in the past. If you remeber that i-- is the same as i,i=i-1 (ignoring the possible use of a processor pos-decrement instruction) It's very similar to the way copying of strings in C, which goes back at least to UNIX, 6th edition (care of the Lions book, 1977) has used this idea:
// This one's from K&R, 2nd ed, p.106
// remember, C strings are null terminated arrays of characters
void strcpy(char *s, char *t)
{
   while(*s++ = *t++)
      ;
}

(say, is the x86 actually able to make use of pre/post-inc/decrements, or is that just a leftover from the PDP-11 days?)

"Independently invented" would be about right for what xriso has done. The idea behind while (i--) is called "decrement and test", and it's just about as old as computing. The PDP or the VAX had SOB (Subtract One and conditionally Branch); x86 has LOOP and the super-tight REP. Other architectures, I'm sure, have their own implementations of the concept.

Looking further back, Babbage's plans for the analytical engine clearly included the idea of decrement-and-test loops for repetition (as in exponentiation), and a theoretical computer called the register machine is interesting because it's known to be Turing complete; the register machine has for "hardware" a fixed number of registers holding natural numbers, and its programs are based around only two operations: "increment" and "decrement and test". A register machine with only two registers can compute any computable result. It might take a horribly long time to do it, though.

 

 

She used to be a programmer

                                                                backwhen

 

I used to watch her small fingers on a keyboard

fluttering left to                                            right 

 

She used to work the late shift at techsupport

one pen behind one ear,  the other between                  her teeth

 

I used to wonder what I would say to her 

if I had the chance to speak to her                                                              alone

 

then the chance came and I said    

nothing                                                                                  nothing at all 

 

I think she shrugged her shoulders when she walked away

maybe I                                                                                                                        imagined it 

 

/dev/full  /dev/null

Log in or register to write something here or to contact authors.