Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > about shifting

Reply
Thread Tools

about shifting

 
 
Charlie Gordon
Guest
Posts: n/a
 
      09-20-2007
"Kenneth Brody" <(E-Mail Removed)> a écrit dans le message de news:
http://www.velocityreviews.com/forums/(E-Mail Removed)...
> 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.


 
Reply With Quote
 
 
 
 
Ark Khasin
Guest
Posts: n/a
 
      09-21-2007
Richard Bos wrote:
> lak <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
Charlie Gordon
Guest
Posts: n/a
 
      09-21-2007
"Ark Khasin" <(E-Mail Removed)> a écrit dans le message de news:
4sEIi.6556$Yb2.2730@trndny08...
> Richard Bos wrote:
>> lak <(E-Mail Removed)> 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.


 
Reply With Quote
 
Ark Khasin
Guest
Posts: n/a
 
      09-21-2007
Charlie Gordon wrote:
> "Ark Khasin" <(E-Mail Removed)> a écrit dans le message de news:
> 4sEIi.6556$Yb2.2730@trndny08...
>> Richard Bos wrote:
>>> lak <(E-Mail Removed)> 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

 
Reply With Quote
 
Army1987
Guest
Posts: n/a
 
      09-21-2007
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

 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      09-21-2007
Kenneth Brody <(E-Mail Removed)> 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.
 
Reply With Quote
 
Tor Rustad
Guest
Posts: n/a
 
      09-21-2007
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>
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Matrix Shifting a_Conan VHDL 0 08-23-2005 11:51 AM
Question about shifting jahaya@gmail.com VHDL 1 07-22-2005 10:09 AM
Shifting rows to the specified column in POI HSSF vidhya Java 0 07-20-2005 06:21 AM
Basic shifting question Stefan Duenser VHDL 4 12-08-2004 11:00 AM
how to write VHDL for shifting? walala VHDL 3 11-21-2003 09:37 AM



Advertisments