A for loop iterating over the complete range of a variable

Discussion in 'C Programming' started by Joona I Palaste, Aug 29, 2004.

  1. Reading Skybuck Flying's obvious troll message, I thought of how to
    properly do a for loop that would iterate over the complete range of
    an unsigned variable. As you all know, Skybuck's method won't work.
    There are a number of other ways. You could use a wider type to do the
    counting, but that would be cheating. You could also handle either the
    first or last iteration as a special case outside the loop, but then it
    would be more than a loop. You could make a very big array of integer
    flags to tell whether you've already visited a value, but that would
    consume too much memory.
    So I settled down to this version. Assume unsigned short is 16 bits
    wide.

    int stop = 0;
    unsigned short i;
    for (i=0; !stop; stop = ++i==0) {
    /* do something */
    }

    Any more elegant solutions out there?

    --
    /-- Joona Palaste () ------------- Finland --------\
    \-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
    "Ice cream sales somehow cause drownings: both happen in summer."
    - Antti Voipio & Arto Wikla
     
    Joona I Palaste, Aug 29, 2004
    #1
    1. Advertising

  2. Joona I Palaste <> scribbled the following:
    > So I settled down to this version. Assume unsigned short is 16 bits
    > wide.


    Actually you don't need to assume that...

    > int stop = 0;
    > unsigned short i;
    > for (i=0; !stop; stop = ++i==0) {
    > /* do something */
    > }


    > Any more elegant solutions out there?


    --
    /-- Joona Palaste () ------------- Finland --------\
    \-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
    "I wish someone we knew would die so we could leave them flowers."
    - A 6-year-old girl, upon seeing flowers in a cemetery
     
    Joona I Palaste, Aug 29, 2004
    #2
    1. Advertising

  3. On Sun, 29 Aug 2004, Joona I Palaste wrote:
    >
    > Reading Skybuck Flying's obvious troll message, I thought of how to
    > properly do a for loop that would iterate over the complete range of
    > an unsigned variable. As you all know, Skybuck's method won't work.
    > There are a number of other ways. You could use a wider type to do the
    > counting, but that would be cheating. You could also handle either the
    > first or last iteration as a special case outside the loop, but then it
    > would be more than a loop. You could make a very big array of integer
    > flags to tell whether you've already visited a value, but that would
    > consume too much memory.
    > So I settled down to this version. Assume unsigned short is 16 bits
    > wide.
    >
    > int stop = 0;
    > unsigned short i;
    > for (i=0; !stop; stop = ++i==0) {
    > /* do something */
    > }
    >
    > Any more elegant solutions out there?


    I'm sure you've seen the solution that gets posted every time someone
    claims it's hard to do:

    unsigned short i = 0;
    do {
    /* do something */
    } while (++i != 0);

    It's not a 'for' loop, but it works and is easy to remember and write.
    I guess you could use a 'for' loop similar to yours, but it would still
    be slower and use a temporary variable: [UNTESTED CODE]

    unsigned short i;
    int tmp;
    for (tmp=0, i=0; i || !tmp; ++i, tmp=1) {
    /* do something */
    }

    -Arthur
     
    Arthur J. O'Dwyer, Aug 29, 2004
    #3
  4. In article <cgt24f$9um$>,
    Joona I Palaste <> wrote:

    >int stop = 0;
    >unsigned short i;
    >for (i=0; !stop; stop = ++i==0) {
    > /* do something */
    >}


    If you use a for loop, you are bound to need some extra variable, since
    the test at the start has to succeed 65536 times and fail once, so you
    need 65537 states.

    You can avoid the use of an extra variable by using a do ... while
    loop, which tests at the end and therefore needs to succeed only 65535
    times:

    i = 0;
    do {
    /* do something */
    i++;
    } while(i != 0);

    -- Richard
     
    Richard Tobin, Aug 29, 2004
    #4
  5. Joona I Palaste

    Ed Morton Guest

    Joona I Palaste wrote:
    > Reading Skybuck Flying's obvious troll message, I thought of how to
    > properly do a for loop that would iterate over the complete range of
    > an unsigned variable. As you all know, Skybuck's method won't work.
    > There are a number of other ways. You could use a wider type to do the
    > counting, but that would be cheating. You could also handle either the
    > first or last iteration as a special case outside the loop, but then it
    > would be more than a loop. You could make a very big array of integer
    > flags to tell whether you've already visited a value, but that would
    > consume too much memory.
    > So I settled down to this version. Assume unsigned short is 16 bits
    > wide.
    >
    > int stop = 0;
    > unsigned short i;
    > for (i=0; !stop; stop = ++i==0) {
    > /* do something */
    > }
    >
    > Any more elegant solutions out there?
    >


    How about:

    unsigned short i;
    for (i=0; ++i;) {
    /* do something */
    }

    For the general case where i might be getting incremented by some number
    other than 1 and so won't necessarily have the value zero when it loops
    around (e.g. 13 in the following example), this might be better:

    unsigned short i, j;
    for (i=0, j=0; i >= j; j=i, i+=13) {
    /* do something */
    }

    Regards,

    Ed.
     
    Ed Morton, Aug 29, 2004
    #5
  6. In article <cgt24f$9um$>,
    Joona I Palaste <> wrote:

    > Reading Skybuck Flying's obvious troll message, I thought of how to
    > properly do a for loop that would iterate over the complete range of
    > an unsigned variable. As you all know, Skybuck's method won't work.
    > There are a number of other ways. You could use a wider type to do the
    > counting, but that would be cheating. You could also handle either the
    > first or last iteration as a special case outside the loop, but then it
    > would be more than a loop. You could make a very big array of integer
    > flags to tell whether you've already visited a value, but that would
    > consume too much memory.
    > So I settled down to this version. Assume unsigned short is 16 bits
    > wide.
    >
    > int stop = 0;
    > unsigned short i;
    > for (i=0; !stop; stop = ++i==0) {
    > /* do something */
    > }
    >
    > Any more elegant solutions out there?


    i = 0;
    do {
    <statements>
    ++i;
    } while (i != 0);

    Doing the same for signed int in a portable way seems to be difficult.
     
    Christian Bau, Aug 29, 2004
    #6
  7. Joona I Palaste

    CBFalconer Guest

    Joona I Palaste wrote:
    >
    > Reading Skybuck Flying's obvious troll message, I thought of how to
    > properly do a for loop that would iterate over the complete range of
    > an unsigned variable. As you all know, Skybuck's method won't work.
    > There are a number of other ways. You could use a wider type to do the
    > counting, but that would be cheating. You could also handle either the
    > first or last iteration as a special case outside the loop, but then it
    > would be more than a loop. You could make a very big array of integer
    > flags to tell whether you've already visited a value, but that would
    > consume too much memory.
    > So I settled down to this version. Assume unsigned short is 16 bits
    > wide.
    >
    > int stop = 0;
    > unsigned short i;
    > for (i=0; !stop; stop = ++i==0) {
    > /* do something */
    > }
    >
    > Any more elegant solutions out there?


    You need a loop that postpones the test until after the first
    iteration. For example:

    unsigned int i;

    i = -1;
    do {
    i++;
    /* stuff */
    } while (i < UINT_MAX);

    or

    i = 0;
    do {
    /* stuff */
    } while (0U != ++i);

    --
    A: Because it fouls the order in which people normally read text.
    Q: Why is top-posting such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    CBFalconer, Aug 29, 2004
    #7
  8. Christian Bau <> writes:
    [...]
    > i = 0;
    > do {
    > <statements>
    > ++i;
    > } while (i != 0);
    >
    > Doing the same for signed int in a portable way seems to be difficult.


    int i = INT_MIN;
    while (1) {
    <statements>
    if (i == INT_MAX) break;
    i ++;
    }

    (Don't try this at home; depending on how fast your machine is,
    iterating over a 32-bit int type could take several minutes and annoy
    other users.)

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, Aug 29, 2004
    #8
  9. Joona I Palaste

    Ben Pfaff Guest

    Keith Thompson <> writes:

    > (Don't try this at home; depending on how fast your machine is,
    > iterating over a 32-bit int type could take several minutes and annoy
    > other users.)


    Most home machines are single-user :)
    --
    "Some people *are* arrogant, and others read the FAQ."
    --Chris Dollin
     
    Ben Pfaff, Aug 29, 2004
    #9
  10. Joona I Palaste

    Tim Rentsch Guest

    Joona I Palaste <> writes:

    > Reading Skybuck Flying's obvious troll message, I thought of how to
    > properly do a for loop that would iterate over the complete range of
    > an unsigned variable.
    >
    > [snip]
    >
    > Any more elegant solutions out there?



    The code


    if( i = LOWER_BOUND, i <= UPPER_BOUND ) do {

    /* stuff to do */

    } while( i++ != UPPER_BOUND );


    does the loop body once for each value of 'i' in the closed
    interval [ LOWER_BOUND .. UPPER_BOUND ] whatever the bounds are (*),
    and doesn't rely on any wraparound tricks. Any decent compiler
    would optimize away the initial test if LOWER_BOUND and UPPER_BOUND
    were known at compile time.

    (*) As long as they are inside the range of the type of 'i'.
    Being outside the range should also should be detected by
    any reasonably decent compiler.
     
    Tim Rentsch, Aug 29, 2004
    #10
  11. Joona I Palaste

    pete Guest

    Arthur J. O'Dwyer wrote:
    >
    > On Sun, 29 Aug 2004, Joona I Palaste wrote:


    > > unsigned short i;
    > > for (i=0; !stop; stop = ++i==0) {


    > > Any more elegant solutions out there?


    > unsigned short i = 0;


    > } while (++i != 0);


    Those ain't elegant.
    ++i;
    means the same thing as
    i = i + 1;

    If INT_MAX equals USHRT_MAX, as it may,
    then you have undefined behavior when i has the value of INT_MAX
    and you try to increment it.

    --
    pete
     
    pete, Aug 30, 2004
    #11
  12. On Mon, 30 Aug 2004, pete wrote:
    >
    > Arthur J. O'Dwyer wrote:
    >
    >> unsigned short i = 0;

    [...]
    >> } while (++i != 0);

    >
    > Those ain't elegant.
    > ++i;
    > means the same thing as
    > i = i + 1;
    >
    > If INT_MAX equals USHRT_MAX, as it may,
    > then you have undefined behavior when i has the value of INT_MAX
    > and you try to increment it.


    I guess you're right. What's the fix? Would

    } while (i=(unsigned short)i+(unsigned short)1);

    fix the UB? (And also, it seems odd that '++i' should mean the same
    as 'i=i+1', promotions and all; can I have C&V for that, please?)

    -Arthur
     
    Arthur J. O'Dwyer, Aug 30, 2004
    #12
  13. Joona I Palaste

    Ben Pfaff Guest

    "Arthur J. O'Dwyer" <> writes:

    > (And also, it seems odd that '++i' should mean the same
    > as 'i=i+1', promotions and all; can I have C&V for that, please?)


    That one's easy. First, in section 6.5.3.1:

    2 The value of the operand of the prefix ++ operator is incremented. The result is the new
    value of the operand after incrementation. The expression ++E is equivalent to (E+=1).
    See the discussions of additive operators and compound assignment for information on
    constraints, types, side effects, and conversions and the effects of operations on pointers.

    Then in section 6.5.16.2:

    3 A compound assignment of the form E1 op = E2 differs from the simple assignment
    expression E1 = E1 op (E2) only in that the lvalue E1 is evaluated only once.

    --
    "I've been on the wagon now for more than a decade. Not a single goto
    in all that time. I just don't need them any more. I don't even use
    break or continue now, except on social occasions of course. And I
    don't get carried away." --Richard Heathfield
     
    Ben Pfaff, Aug 30, 2004
    #13
  14. Joona I Palaste

    pete Guest

    Arthur J. O'Dwyer wrote:
    >
    > On Mon, 30 Aug 2004, pete wrote:
    > >
    > > Arthur J. O'Dwyer wrote:
    > >
    > >> unsigned short i = 0;

    > [...]
    > >> } while (++i != 0);

    > >
    > > Those ain't elegant.
    > > ++i;
    > > means the same thing as
    > > i = i + 1;
    > >
    > > If INT_MAX equals USHRT_MAX, as it may,
    > > then you have undefined behavior when i has the value of INT_MAX
    > > and you try to increment it.

    >
    > I guess you're right. What's the fix? Would
    >
    > } while (i=(unsigned short)i+(unsigned short)1);
    >
    > fix the UB?


    No.
    (sizeof((short)0 + (short)0)) equals (sizeof(int)).

    --
    pete
     
    pete, Aug 30, 2004
    #14
  15. "Arthur J. O'Dwyer" <> wrote in message
    news:p...
    > On Mon, 30 Aug 2004, pete wrote:
    > > Arthur J. O'Dwyer wrote:
    > >
    > > > unsigned short i = 0;

    > [...]
    > > > } while (++i != 0);

    > >
    > > Those ain't elegant.
    > > ++i;
    > > means the same thing as
    > > i = i + 1;
    > >
    > > If INT_MAX equals USHRT_MAX, as it may,
    > > then you have undefined behavior when i has the value of INT_MAX
    > > and you try to increment it.

    >
    > I guess you're right. What's the fix? Would
    >
    > } while (i=(unsigned short)i+(unsigned short)1);
    >
    > fix the UB?


    No. Even though you cast the operands of +, they are still subject to
    integral promotion prior to the addition taking place.

    The fix is trivial though...

    unsigned short i = 0;
    do {

    } while (i += 1u);

    --
    Peter
     
    Peter Nilsson, Aug 30, 2004
    #15
  16. Joona I Palaste

    xarax Guest

    "Ben Pfaff" <> wrote in message
    news:...
    > Keith Thompson <> writes:
    >
    > > (Don't try this at home; depending on how fast your machine is,
    > > iterating over a 32-bit int type could take several minutes and annoy
    > > other users.)

    >
    > Most home machines are single-user :)


    Yes, but if he does it, I'll still be annoyed about it. ;)
     
    xarax, Aug 30, 2004
    #16
  17. Joona I Palaste

    Fao, Sean Guest

    Keith Thompson wrote:
    > Christian Bau <> writes:
    > [...]
    >
    >>i = 0;
    >>do {
    >> <statements>
    >> ++i;
    >>} while (i != 0);
    >>
    >>Doing the same for signed int in a portable way seems to be difficult.

    >
    >
    > int i = INT_MIN;
    > while (1) {
    > <statements>
    > if (i == INT_MAX) break;
    > i ++;


    ITYM i++; ;-)

    Sean
    --
    Sean Fao
    CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
    CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>
     
    Fao, Sean, Sep 1, 2004
    #17
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Steffen Beyer
    Replies:
    2
    Views:
    1,086
    Steffen Beyer
    Oct 27, 2004
  2. adam carr
    Replies:
    8
    Views:
    814
    Steven D'Aprano
    Nov 28, 2008
  3. carl
    Replies:
    5
    Views:
    2,379
    James Kanze
    Nov 25, 2009
  4. Ángel José Riesgo
    Replies:
    13
    Views:
    496
    Ángel José Riesgo
    Feb 18, 2011
  5. Isaac Won
    Replies:
    9
    Views:
    381
    Ulrich Eckhardt
    Mar 4, 2013
Loading...

Share This Page