about shifting

Discussion in 'C Programming' started by lak, Sep 20, 2007.

  1. lak

    lak Guest

    i know left and right shift normally,but i cant know what happens if
    it is negative.
    for example
    int x=-2;
    x<<=1;//what happens here
     
    lak, Sep 20, 2007
    #1
    1. Advertising

  2. lak wrote:
    > i know left and right shift normally,but i cant know what happens if
    > it is negative.
    > for example
    > int x=-2;
    > x<<=1;//what happens here
    >


    nothing different from usual.. the bit representation of -2 is shifted
    one bit to the left...

    > cat test_shift.c


    #include <stdio.h>
    int main(void)
    {

    int k = -1;
    printf("k is %d (%x)\n", k, k);
    k<<=4;
    printf("k is %d (%x)\n", k, k);

    return (0);
    }

    > gcc -Wall -o test_shift test_shift.c && ./test_shift

    k is -1 (ffffffff)
    k is -16 (fffffff0)

    Pietro Cerutti
     
    Pietro Cerutti, Sep 20, 2007
    #2
    1. Advertising

  3. lak

    Richard Bos Guest

    lak <> wrote:

    > i know left and right shift normally,but i cant know what happens if
    > it is negative.
    > for example
    > int x=-2;
    > x<<=1;//what happens here


    That is correct: you cannot know that.

    From paragraph 6.5.7 in the ISO C Standard:

    # 4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated
    # bits are filled with zeros. If E1 has an unsigned type, the value of
    # the result is E1 x 2 E2 ,reduced modulo one more than the maximum
    # value representable in the result type. If E1 has a signed type and
    # nonnegative value, and E1 x 2 E2 is representable in the result
    # type, then that is the resulting value; otherwise, the behavior is
    # undefined. ^^^^^^^^^^^^^^^^^^^^^^^^^^
    ^^^^^^^^^

    Note the under^^^lined bit. Since in your case x is neither an unsigned
    integer, nor a signed integer with a positive value, the behaviour of
    your code is undefined; and this means that, as far as ISO C is
    concerned, you cannot know what happens. (It may be possible to discover
    what happens on a particular computer using a particular compiler with
    particular compilation settings, but I advise against it; on the next
    system, or even on the next level of optimisation, the result can easily
    be different.)

    Richard
     
    Richard Bos, Sep 20, 2007
    #3
  4. "Richard Bos" <> a écrit dans le message de news:
    4all.nl...
    > lak <> wrote:
    >
    >> i know left and right shift normally,but i cant know what happens if
    >> it is negative.
    >> for example
    >> int x=-2;
    >> x<<=1;//what happens here

    >
    > That is correct: you cannot know that.
    >
    > From paragraph 6.5.7 in the ISO C Standard:
    >
    > # 4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated
    > # bits are filled with zeros. If E1 has an unsigned type, the value of
    > # the result is E1 x 2 E2 ,reduced modulo one more than the maximum
    > # value representable in the result type. If E1 has a signed type and
    > # nonnegative value, and E1 x 2 E2 is representable in the result
    > # type, then that is the resulting value; otherwise, the behavior is
    > # undefined. ^^^^^^^^^^^^^^^^^^^^^^^^^^
    > ^^^^^^^^^
    >
    > Note the under^^^lined bit. Since in your case x is neither an unsigned
    > integer, nor a signed integer with a positive value, the behaviour of
    > your code is undefined; and this means that, as far as ISO C is
    > concerned, you cannot know what happens. (It may be possible to discover
    > what happens on a particular computer using a particular compiler with
    > particular compilation settings, but I advise against it; on the next
    > system, or even on the next level of optimisation, the result can easily
    > be different.)


    Richard is correct.
    However, if you expected x <<= 1 to be equivalent to x += x, as would
    "normally" be the case on regular 2s-complement machines, you might as well
    write the latter.

    --
    Chqrlie.
     
    Charlie Gordon, Sep 20, 2007
    #4
  5. Pietro Cerutti wrote:
    > lak wrote:
    >> i know left and right shift normally,but i cant know what happens if
    >> it is negative.
    >> for example
    >> int x=-2;
    >> x<<=1;//what happens here
    >>

    >
    > nothing different from usual.. the bit representation of -2 is shifted
    > one bit to the left...


    Umh, I have to apologize.. my sentence is actually incorrect. That's
    true for right-shifting, while for left-shifting a negative left-hand
    operand invokes UB

    --
    Pietro Cerutti
     
    Pietro Cerutti, Sep 20, 2007
    #5
  6. Nit-pick non-UB (was Re: about shifting)

    Charlie Gordon wrote:
    [... bit-shifting negative numbers ...]
    > However, if you expected x <<= 1 to be equivalent to x += x, as would
    > "normally" be the case on regular 2s-complement machines, you might
    > as well write the latter.


    Okay, nit-pick time related to UB.

    Why doesn't the statement:

    x += x;

    violate 6.5p2:

    Between the previous and next sequence point an object shall
    have its stored value modified at most once by the evaluation
    of an expression. Furthermore, the prior value shall be read
    only to determine the value to be stored.

    Yes, I see that footnote 71 says that "i = i + 1" is allowed by the
    paragraph, but why is the "x" on the right of "+=" not violating the
    "shall be read only to determine the value to be stored"? How is
    this different from "y = x + x++;" in the use of "x"?

    Obviously, something like "x += x;" must be allowed, but what is it
    about 6.5p2 that allows it?

    --
    +-------------------------+--------------------+-----------------------+
    | Kenneth J. Brody | www.hvcomputer.com | #include |
    | kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h> |
    +-------------------------+--------------------+-----------------------+
    Don't e-mail me at: <mailto:>
     
    Kenneth Brody, Sep 20, 2007
    #6
  7. lak

    CBFalconer Guest

    Pietro Cerutti wrote:
    > Pietro Cerutti wrote:
    >> lak wrote:
    >>
    >>> i know left and right shift normally,but i cant know what
    >>> happens if it is negative. for example
    >>> int x=-2;
    >>> x<<=1;//what happens here

    >>
    >> nothing different from usual.. the bit representation of -2 is
    >> shifted one bit to the left...

    >
    > Umh, I have to apologize.. my sentence is actually incorrect.
    > That's true for right-shifting, while for left-shifting a
    > negative left-hand operand invokes UB


    Since lak appears to be a newbie, explain that UB means "undefined
    behaviour". In other words, don't do that. Also for positive
    operands that overflow.

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>



    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Sep 20, 2007
    #7
  8. lak

    Flash Gordon Guest

    Pietro Cerutti wrote, On 20/09/07 14:45:
    > Pietro Cerutti wrote:
    >> lak wrote:
    >>> i know left and right shift normally,but i cant know what happens if
    >>> it is negative.
    >>> for example
    >>> int x=-2;
    >>> x<<=1;//what happens here
    >>>

    >> nothing different from usual.. the bit representation of -2 is shifted
    >> one bit to the left...

    >
    > Umh, I have to apologize.. my sentence is actually incorrect. That's
    > true for right-shifting, while for left-shifting a negative left-hand
    > operand invokes UB


    For right shifting it is implementation defined, so you were just wrong.
    --
    Flash Gordon
     
    Flash Gordon, Sep 20, 2007
    #8
  9. lak

    Flash Gordon Guest

    Charlie Gordon wrote, On 20/09/07 13:51:
    > "Richard Bos" <> a écrit dans le message de news:
    > 4all.nl...
    >> lak <> wrote:
    >>
    >>> i know left and right shift normally,but i cant know what happens if
    >>> it is negative.
    >>> for example
    >>> int x=-2;
    >>> x<<=1;//what happens here

    >> That is correct: you cannot know that.


    <snip>

    > Richard is correct.
    > However, if you expected x <<= 1 to be equivalent to x += x, as would
    > "normally" be the case on regular 2s-complement machines, you might as well
    > write the latter.


    Personally I would write it as x *= 2.
    --
    Flash Gordon
     
    Flash Gordon, Sep 20, 2007
    #9
  10. lak

    user923005 Guest

    Re: Nit-pick non-UB (was Re: about shifting)

    On Sep 20, 10:33 am, Kenneth Brody <> wrote:
    > Charlie Gordon wrote:
    >
    > [... bit-shifting negative numbers ...]
    >
    > > However, if you expected x <<= 1 to be equivalent to x += x, as would
    > > "normally" be the case on regular 2s-complement machines, you might
    > > as well write the latter.

    >
    > Okay, nit-pick time related to UB.
    >
    > Why doesn't the statement:
    >
    > x += x;
    >
    > violate 6.5p2:
    >
    > Between the previous and next sequence point an object shall
    > have its stored value modified at most once by the evaluation
    > of an expression. Furthermore, the prior value shall be read
    > only to determine the value to be stored.
    >
    > Yes, I see that footnote 71 says that "i = i + 1" is allowed by the
    > paragraph, but why is the "x" on the right of "+=" not violating the
    > "shall be read only to determine the value to be stored"? How is
    > this different from "y = x + x++;" in the use of "x"?
    >
    > Obviously, something like "x += x;" must be allowed, but what is it
    > about 6.5p2 that allows it?


    "Furthermore, the prior value shall be read only to determine the
    value to be stored."

    Quite frankly, in this case, I simply don't see how it would be
    possible for the compiler to get it wrong.

    For an instance like:

    i = ++i;

    there are two modifications of i, so it's right out.

    But how is:
    x += x;
    more dangerous than (for instance):
    x = x;
    Both of which have to examine the contents of x use those contents to
    modify x (though this second instance can be thrown out by the
    compiler if it chooses because of the 'as if' rule.)

    For the instance of:
    y = x + x++;
    We don't even need the y. This is also undefined behavior:

    #include <stdlib.h>
    int t(void)
    {
    int x = rand();
    return x + x++;
    }

    We are adding x + <something>
    We are also incrementing x.
    There is no sequence point.
     
    user923005, Sep 20, 2007
    #10
  11. Re: Nit-pick non-UB (was Re: about shifting)

    "Kenneth Brody" <> a écrit dans le message de news:
    ...
    > Charlie Gordon wrote:
    > [... bit-shifting negative numbers ...]
    >> However, if you expected x <<= 1 to be equivalent to x += x, as would
    >> "normally" be the case on regular 2s-complement machines, you might
    >> as well write the latter.

    >
    > Okay, nit-pick time related to UB.
    >
    > Why doesn't the statement:
    >
    > x += x;
    >
    > violate 6.5p2:
    >
    > Between the previous and next sequence point an object shall
    > have its stored value modified at most once by the evaluation
    > of an expression. Furthermore, the prior value shall be read
    > only to determine the value to be stored.
    >
    > Yes, I see that footnote 71 says that "i = i + 1" is allowed by the
    > paragraph, but why is the "x" on the right of "+=" not violating the
    > "shall be read only to determine the value to be stored"? How is
    > this different from "y = x + x++;" in the use of "x"?
    >
    > Obviously, something like "x += x;" must be allowed, but what is it
    > about 6.5p2 that allows it?


    x is modified only once, and its value is read only to determine the value
    to be stored, once or twice depending on quality of implementation or
    presence of volatile qualifier on x's definition.

    Change x <<= N into x *= 1 << N to get rid of the problem with negative x,
    as long as the multiplication does not overflow. Also note that *all*
    current architectures use two's complement representation for integers, and
    implement left shifting on negative numbers consistently.

    --
    Chqrlie.
     
    Charlie Gordon, Sep 20, 2007
    #11
  12. lak

    Ark Khasin Guest

    Richard Bos wrote:
    > lak <> wrote:
    >
    >> i know left and right shift normally,but i cant know what happens if
    >> it is negative.
    >> for example
    >> int x=-2;
    >> x<<=1;//what happens here

    >
    > That is correct: you cannot know that.
    >
    > From paragraph 6.5.7 in the ISO C Standard:
    >
    > # 4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated
    > # bits are filled with zeros. If E1 has an unsigned type, the value of
    > # the result is E1 x 2 E2 ,reduced modulo one more than the maximum
    > # value representable in the result type. If E1 has a signed type and
    > # nonnegative value, and E1 x 2 E2 is representable in the result
    > # type, then that is the resulting value; otherwise, the behavior is
    > # undefined. ^^^^^^^^^^^^^^^^^^^^^^^^^^
    > ^^^^^^^^^
    >
    > Note the under^^^lined bit. Since in your case x is neither an unsigned
    > integer, nor a signed integer with a positive value, the behaviour of
    > your code is undefined; and this means that, as far as ISO C is
    > concerned, you cannot know what happens. (It may be possible to discover
    > what happens on a particular computer using a particular compiler with
    > particular compilation settings, but I advise against it; on the next
    > system, or even on the next level of optimisation, the result can easily
    > be different.)
    >
    > Richard

    I am afraid I don't understand shifts anymore. I suppose(d) that on
    32-bit machine
    insigned x, y;
    y = 32U; //where the compiler doesn't see it
    (x<<y)==0U && (x>>y)==0U
    All ARM compilers I've seen, the effective calculation is
    x << (y & 31U) and x << (y & 31U)
    (because that's how the CPU instructions work)
    Is this compliant?

    -- Ark
     
    Ark Khasin, Sep 21, 2007
    #12
  13. "Ark Khasin" <> a écrit dans le message de news:
    4sEIi.6556$Yb2.2730@trndny08...
    > Richard Bos wrote:
    >> lak <> wrote:
    >>
    >>> i know left and right shift normally,but i cant know what happens if
    >>> it is negative.
    >>> for example
    >>> int x=-2;
    >>> x<<=1;//what happens here

    >>
    >> That is correct: you cannot know that. From paragraph 6.5.7 in the ISO C
    >> Standard:
    >>
    >> # 4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated
    >> # bits are filled with zeros. If E1 has an unsigned type, the value of
    >> # the result is E1 x 2 E2 ,reduced modulo one more than the maximum
    >> # value representable in the result type. If E1 has a signed type and
    >> # nonnegative value, and E1 x 2 E2 is representable in the result
    >> # type, then that is the resulting value; otherwise, the behavior is
    >> # undefined. ^^^^^^^^^^^^^^^^^^^^^^^^^^
    >> ^^^^^^^^^
    >>
    >> Note the under^^^lined bit. Since in your case x is neither an unsigned
    >> integer, nor a signed integer with a positive value, the behaviour of
    >> your code is undefined; and this means that, as far as ISO C is
    >> concerned, you cannot know what happens. (It may be possible to discover
    >> what happens on a particular computer using a particular compiler with
    >> particular compilation settings, but I advise against it; on the next
    >> system, or even on the next level of optimisation, the result can easily
    >> be different.)
    >>
    >> Richard

    > I am afraid I don't understand shifts anymore. I suppose(d) that on 32-bit
    > machine
    > insigned x, y;
    > y = 32U; //where the compiler doesn't see it
    > (x<<y)==0U && (x>>y)==0U
    > All ARM compilers I've seen, the effective calculation is
    > x << (y & 31U) and x << (y & 31U)
    > (because that's how the CPU instructions work)
    >
    > Is this compliant?


    C99 6.5.7p3 also says: If the value of the right operand is negative or is
    greater than or equal to the width of the promoted left operand, the
    behavior is undefined. So shifting a 32-bit integer by 32 invokes undefined
    behaviour. That covers any harware behaviour whatsoever.

    If you really want that, you need to split the operation:
    (x << 16) << 16 == 0 && (x >> 16) >> 16 == 0

    --
    Chqrlie.
     
    Charlie Gordon, Sep 21, 2007
    #13
  14. lak

    Ark Khasin Guest

    Charlie Gordon wrote:
    > "Ark Khasin" <> a écrit dans le message de news:
    > 4sEIi.6556$Yb2.2730@trndny08...
    >> Richard Bos wrote:
    >>> lak <> wrote:
    >>>
    >>>> i know left and right shift normally,but i cant know what happens if
    >>>> it is negative.
    >>>> for example
    >>>> int x=-2;
    >>>> x<<=1;//what happens here
    >>> That is correct: you cannot know that. From paragraph 6.5.7 in the ISO C
    >>> Standard:
    >>>
    >>> # 4 The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated
    >>> # bits are filled with zeros. If E1 has an unsigned type, the value of
    >>> # the result is E1 x 2 E2 ,reduced modulo one more than the maximum
    >>> # value representable in the result type. If E1 has a signed type and
    >>> # nonnegative value, and E1 x 2 E2 is representable in the result
    >>> # type, then that is the resulting value; otherwise, the behavior is
    >>> # undefined. ^^^^^^^^^^^^^^^^^^^^^^^^^^
    >>> ^^^^^^^^^
    >>>
    >>> Note the under^^^lined bit. Since in your case x is neither an unsigned
    >>> integer, nor a signed integer with a positive value, the behaviour of
    >>> your code is undefined; and this means that, as far as ISO C is
    >>> concerned, you cannot know what happens. (It may be possible to discover
    >>> what happens on a particular computer using a particular compiler with
    >>> particular compilation settings, but I advise against it; on the next
    >>> system, or even on the next level of optimisation, the result can easily
    >>> be different.)
    >>>
    >>> Richard

    >> I am afraid I don't understand shifts anymore. I suppose(d) that on 32-bit
    >> machine
    >> insigned x, y;
    >> y = 32U; //where the compiler doesn't see it
    >> (x<<y)==0U && (x>>y)==0U
    >> All ARM compilers I've seen, the effective calculation is
    >> x << (y & 31U) and x << (y & 31U)
    >> (because that's how the CPU instructions work)
    >>
    >> Is this compliant?

    >
    > C99 6.5.7p3 also says: If the value of the right operand is negative or is
    > greater than or equal to the width of the promoted left operand, the
    > behavior is undefined. So shifting a 32-bit integer by 32 invokes undefined
    > behaviour. That covers any harware behaviour whatsoever.
    >
    > If you really want that, you need to split the operation:
    > (x << 16) << 16 == 0 && (x >> 16) >> 16 == 0
    >

    Thanks. I should have known better indeed.
    -- Ark
     
    Ark Khasin, Sep 21, 2007
    #14
  15. lak

    Army1987 Guest

    Re: Nit-pick non-UB (was Re: about shifting)

    On Thu, 20 Sep 2007 13:33:21 -0400, Kenneth Brody wrote:

    > Why doesn't the statement:
    >
    > x += x;
    >
    > violate 6.5p2:
    >
    > Between the previous and next sequence point an object shall
    > have its stored value modified at most once by the evaluation
    > of an expression. Furthermore, the prior value shall be read
    > only to determine the value to be stored.
    >
    > Yes, I see that footnote 71 says that "i = i + 1" is allowed by the
    > paragraph, but why is the "x" on the right of "+=" not violating the
    > "shall be read only to determine the value to be stored"? How is
    > this different from "y = x + x++;" in the use of "x"?
    >
    > Obviously, something like "x += x;" must be allowed, but what is it
    > about 6.5p2 that allows it?

    x is modified only once, and it is only read to determine the
    value to be stored. Right? I think the last sentence in that quote
    is very mysterious. There have been endless discussions about
    whether list = list->next = malloc(sizeof *list) causes UB. And a
    sufficiently bizarre interpretation of that sentence would mean
    that
    x = 0 * x + rand() causes UB, and
    x = 1 * x + abs(0) doesn't. I definitely think that this isn't the
    intent. Anyway, I've developed a paranoia of not using the same
    lvalue twice in an expression, e.g. I'd rather write i *= -1 than
    i = -i, or u ^= UINT_MAX than u = ~u. (At least this helps to
    write macros which evaluate its argument exactly once, but is it
    *really* necessary when written directly in the code?)

    --
    Army1987 (Replace "NOSPAM" with "email")
    If you're sending e-mail from a Windows machine, turn off Microsoft's
    stupid “Smart Quotes†feature. This is so you'll avoid sprinkling garbage
    characters through your mail. -- Eric S. Raymond and Rick Moen
     
    Army1987, Sep 21, 2007
    #15
  16. Re: Nit-pick non-UB (was Re: about shifting)

    Kenneth Brody <> writes:

    > Charlie Gordon wrote:
    > [... bit-shifting negative numbers ...]
    >> However, if you expected x <<= 1 to be equivalent to x += x, as would
    >> "normally" be the case on regular 2s-complement machines, you might
    >> as well write the latter.

    >
    > Okay, nit-pick time related to UB.
    >
    > Why doesn't the statement:
    >
    > x += x;
    >
    > violate 6.5p2:
    >
    > Between the previous and next sequence point an object shall
    > have its stored value modified at most once by the evaluation
    > of an expression. Furthermore, the prior value shall be read
    > only to determine the value to be stored.
    >
    > Yes, I see that footnote 71 says that "i = i + 1" is allowed by the
    > paragraph, but why is the "x" on the right of "+=" not violating the
    > "shall be read only to determine the value to be stored"? How is
    > this different from "y = x + x++;" in the use of "x"?


    Why 'x += x;' is OK has been answered, but why 'y = x + x++;' is not
    might need a bit more discussion. Here, the prior value is read to
    determine both the value to be stored in x and the value of x for the
    addition. The term "read" is important. If the standard had said
    "used" then 'y = 1 + x++;' would be UB (x's prior value is used for a
    purpose other than to determine the value to be stored).

    The prohibition is on more than one part of the expression referring
    to the value of an object whose value the expression modifies. I
    doubt that that wording is any clearer (or I am sure the committee
    would have used it) but it gives another way to look at it.

    --
    Ben.
     
    Ben Bacarisse, Sep 21, 2007
    #16
  17. lak

    Tor Rustad Guest

    lak wrote:
    > i know left and right shift normally,but i cant know what happens if
    > it is negative.
    > for example
    > int x=-2;
    > x<<=1;//what happens here



    A simple rule of thumb, is to do bitwise operations on unsigned types.


    --
    Tor <torust [at] online [dot] no>
     
    Tor Rustad, Sep 21, 2007
    #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. walala
    Replies:
    3
    Views:
    5,364
    Brent Hayhoe
    Nov 21, 2003
  2. Stefan Duenser

    Basic shifting question

    Stefan Duenser, Dec 7, 2004, in forum: VHDL
    Replies:
    4
    Views:
    447
    Stefan Duenser
    Dec 8, 2004
  3. Replies:
    1
    Views:
    471
  4. a_Conan

    Matrix Shifting

    a_Conan, Aug 23, 2005, in forum: VHDL
    Replies:
    0
    Views:
    550
    a_Conan
    Aug 23, 2005
  5. vidhya
    Replies:
    0
    Views:
    473
    vidhya
    Jul 20, 2005
Loading...

Share This Page