A pointer problem from a high school programming contest

This is a discussion on A pointer problem from a high school programming contest within the C++ Programming forums, part of the General Programming Boards category; Hi experts, The code below is from a programming contest, the answer must be given without using a compiler(this test ...

  1. #1
    Registered User
    Join Date
    Jul 2006
    Posts
    25

    A pointer problem from a high school programming contest

    Hi experts,

    The code below is from a programming contest, the answer must be given without using a compiler(this test is on paper).


    The problem: How many '*' does that piece of code prints?
    a) 20
    b) 25
    c) 33
    d) 50
    e) 100

    Code:
    #include<cstdio>
    void f(int i){i--;}
    void g(int i){int*p;p=&i;*p--;}
    void h(int*p){*p--;}
    void i(int*p){int i;i=*p;i--;}
    int main()
    {
    int index=100;
    for(;index>0;index--)
    { printf("*"); f(index); g(index); h(&index); i(&index); }
    }
    I found out 50, but when i put it in compiler i saw that i'm mistaken, the answer seems 100. How can it be? shouldn't function h decrease index too?

    thanks in advance!

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by kolistivra View Post
    I found out 50, but when i put it in compiler i saw that i'm mistaken, the answer seems 100. How can it be? shouldn't function h decrease index too?
    Look carefully at an operator precedence table. *p-- isn't doing what you think it is.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    If I'm not mistaken, each of the *p--'s is generating a bad pointer by decrementing p, then dereferencing the result, either of which generates undefined behavior. So there is no 100&#37; correct answer (though if you assume that *p-- is equivalent to a noop, then it's 100).

  4. #4
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by robatino View Post
    If I'm not mistaken, each of the *p--'s is generating a bad pointer by decrementing p, then dereferencing the result, either of which generates undefined behavior. So there is no 100% correct answer (though if you assume that *p-- is equivalent to a noop, then it's 100).
    It's postfix decrement, so it decrements after the dereference. This is a funny example because although the decrement binds first, its operation happens second.

    You typically see this kind of thing in loops which copy data (usually with increment, not decrement):

    Code:
    type *src, *dst, *end;
    ...
    while(src < end)
        *dst++ = *src++;

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    > It's postfix decrement, so it decrements after the dereference.
    You're right, I don't know what I was thinking since I do this all the time. So it's just the decrement that generates the undefined behavior (though the conclusion is the same).

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by robatino View Post
    > It's postfix decrement, so it decrements after the dereference.
    You're right, I don't know what I was thinking since I do this all the time. So it's just the decrement that generates the undefined behavior (though the conclusion is the same).
    I don't think there's any undefined behavior. The decrement turns the pointer into something undefined, but the function returns immediately so the bogus pointer is never used.

    If merely being in possession of an undefined pointer could lead to undefined behavior, then pretty much every program in the universe is undefined, because whenever you declare a pointer there is a brief period of time before it is initialized:

    Code:
    void nuclear_explosion()
    {
        int *kaboom;
    
        printf("I explode now because kaboom is undefined!\n");
        kaboom = NULL;
    }
    Any platform or compiler where that blows up is just ridiculous. Even if the standard implies it.

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    Actually, I think I remember reading in the standard that there is only one case where you can have a pointer that points to an undefined location, and that is the case of an uninitialized pointer. That is a special case, though, so kaboom is not undefined behavior but decrementing p is.

    The part of the standard I was looking at was not specifically related to this, though, so it is possible that the actual wording is different.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,648
    Actually, I think I remember reading in the standard that there is only one case where you can have a pointer that points to an undefined location, and that is the case of an uninitialized pointer.
    There is at least one other case, that of a pointer that points one past the end of an array.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    What about pointers to out-of-scope variables? Or NULL pointers. Or pointers to freed memory.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    I believe the undefined behavior only occurs when the pointer is actually _assigned_ a bad value. I found the following (http://gcc.gnu.org/onlinedocs/libstd...ors/howto.html) though I don't have an exact reference in the Standard:

    1. You can point anywhere in the array, or to the first element past the end of the array. A pointer that points to one past the end of the array is guaranteed to be as unique as a pointer to somewhere inside the array, so that you can compare such pointers safely.
    2. You can only dereference a pointer that points into an array. If your array pointer points outside the array -- even to just one past the end -- and you dereference it, Bad Things happen.
    3. Strictly speaking, simply pointing anywhere else invokes undefined behavior. Most programs won't puke until such a pointer is actually dereferenced, but the standards leave that up to the platform.

    Edit: Here's a link to the exact part of the Standard that mentions the undefined behavior (see 1161).

    http://c0x.coding-guidelines.com/6.5.6.html
    Last edited by robatino; 04-25-2007 at 04:27 PM.

  11. #11
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by laserlight View Post
    There is at least one other case, that of a pointer that points one past the end of an array.
    I'm not sure if it also includes a pointer to a position immediately before the beginning of an array as well... But if it doesn't, it should. There's no legitimate reason to prevent people from processing an array backwards instead of forwards.

    This is one area where I feel perfectly safe disregarding the standard.

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,648
    What about pointers to out-of-scope variables? Or NULL pointers. Or pointers to freed memory.
    As I understand it, null pointers do not point to any location, so they do not point to any undefined location. The other two look like good examples too.

    I'm not sure if it also includes a pointer to a position immediately before the beginning of an array as well... But if it doesn't, it should.
    I have been searching the C++ standard for a word on this, but it seems to only deal with one past the end pointers explicitly.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by laserlight View Post
    I have been searching the C++ standard for a word on this, but it seems to only deal with one past the end pointers explicitly.
    The C and C++ standards irritate me because they were written under the assumption that a computer could be ANYTHING at all. A computer might work via millions of tiny clowns on unicycles. So the standard ends up disallowing tons of completely reasonable code.

    Any platform where that nuclear_explosion() function blows up is a platform you'll never see me writing code for. At least not in C/C++.

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Quote Originally Posted by brewbuck View Post
    I'm not sure if it also includes a pointer to a position immediately before the beginning of an array as well... But if it doesn't, it should.
    It doesn't. I don't remember the details, but there was a reason involving much more wasted memory if one-past access was allowed at both ends. In any case, it's possible to write loops so they only require it at one end (of course the choice of which end is arbitrary).

  15. #15
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Here's a long and detailed thread on the subject:

    http://groups.google.com/group/comp....18f6cccd56427d

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. pointer to pointer realloc problem
    By prakash0104 in forum C Programming
    Replies: 14
    Last Post: 04-06-2009, 08:53 PM
  2. Replies: 5
    Last Post: 04-04-2009, 03:45 AM
  3. A problem with pointer initialization
    By zyklon in forum C Programming
    Replies: 5
    Last Post: 01-17-2009, 11:42 AM
  4. Problem with function's pointer!
    By Tirania in forum C Programming
    Replies: 5
    Last Post: 11-28-2008, 03:50 AM
  5. towers of hanoi problem
    By aik_21 in forum C Programming
    Replies: 1
    Last Post: 10-02-2004, 01:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21