Arithmetic shift operation in C

[Jean-Claude Arbaut]

Re: Arithmetic shift operation in C




Le 16/06/2005 18:01, dans d8s7pk$ein$1@ne ws1brm.Central. Sun.COM, « Eric
Sosman » <eric.sosman@su n.com> a écrit :
[color=blue]
> Disagreeing with L.K. in this forum carries more than a
> little chance of making oneself ridiculous, but "fools rush
> in" ... Here I go; draw your own conclusions:[/color]

I wouldn't agree with somebody just because of its name ;-)
Just as I would not agree with a math proof just because
a great mathematician has written it.

Still, Lawrence Kirby advice are more than interesting...

[Lawrence Kirby]

Re: Arithmetic shift operation in C

On Thu, 16 Jun 2005 12:41:04 +0200, Jean-Claude Arbaut wrote:

....
[color=blue]
> On modern x86, gcc can eliminate the jump and use a conditionnal move:
>
> movl 4(%esp), %eax
> leal 3(%eax), %edx
> cmpl $-1, %eax
> cmovle %edx, %eax
> sarl $2, %eax
> ret
>
> But that has nothing to do with the OP, it's just an optimization trick.[/color]

The point remains the same, the code demonstrates a difference between
division and arithmetic shifting.

Lawrence

[Tim Rentsch]

Re: Arithmetic shift operation in C

Lawrence Kirby <lknews@netacti ve.co.uk> writes:
[color=blue]
> On Thu, 16 Jun 2005 07:15:58 +0000, Richard Bos wrote:
>[color=green]
> > CBFalconer <cbfalconer@yah oo.com> wrote:
> >[color=darkred]
> >> [snip]
> >>
> >> There is a lot of misinformation in the replies you have received.
> >> Shift operations in C are only portable, and properly defined, on
> >> unsigned objects.[/color]
> >
> > This is not true. They are only portable, and properly defined, on
> > non-negative values. C never shifts objects, it shifts values;[/color]
>
> That's tricky, a shift works at the representation level, and in addition
> the standard defines the effect on values in some circumstances.
>[color=green]
> > and a
> > shift of a signed integer which only involves representable non-negative
> > values is defined.
> > That is, right-shifting a non-negative signed integer works identically
> > to right-shifting an unsigned integer, both in C99 and C89. In C99, a
> > left-shift on a non-negative signed integer is also identical to the
> > operation done on an unsigned integer, as long as the result is
> > representable in the signed type; C89 does seem to leave this case
> > undefined.[/color]
>
> It doesn't define what happens in terms of value but it stil describes
> what happens at the representation level.[/color]

Are we reading different documents? The description I read of the
"Bitwise shift operators" (ISO/IEC 9899:1999 (E), section 6.5.7) talks
only about values, not about representations .

[Lawrence Kirby]

Re: Arithmetic shift operation in C

On Thu, 16 Jun 2005 10:51:50 -0700, Tim Rentsch wrote:

....
[color=blue]
> Are we reading different documents? The description I read of the
> "Bitwise shift operators" (ISO/IEC 9899:1999 (E), section 6.5.7) talks
> only about values, not about representations .[/color]

It talks abouyt thinks like "bit positions" which is a description of
representation rather than value.

Lawrence

[Lawrence Kirby]

Re: Arithmetic shift operation in C

On Thu, 16 Jun 2005 12:01:56 -0400, Eric Sosman wrote:

....
[color=blue]
> The Standard describes the shift operators in terms of
> a binary representation, but I think R.B. is right: they
> operate on values, not on "the" representations .[/color]

You're making a distinction there but it is one that makes a
difference?
[color=blue]
> Consider
> an `int' representation with padding bits: Assuming a shift
> whose result is well-defined, the padding bits do not
> affect any value bits of that result.[/color]

I certainly agree that the standard is talking about non-padding
bits. But given that is this abstract representation you'rer
referring to any different from the underlying object
representation?

....
[color=blue]
> The value/representation question can also be argued
> without introducing exotica like padding bits. How are "bit
> positions" defined in the first place? Not by reference to a
> physical ordering: they could be left-to-right, top-to-bottom,
> scattered in some strange pattern that conserves silicon --
> they could even have no individual physical existence at all
> in a computer built of four-state components each representing
> a pair of bits. Nor can they be ordered by their addresses,
> since even on a bit-addressable machine C has no way to talk
> about the address of anything smaller than a complete `char'.
> No, "bit positions" (and the "left" and "right" directions)
> can only be described in terms of the powers of two in the
> value.[/color]

Agreed. And the representation of an integer type on a particular
platform must attribute binary weightings to the value bits.
[color=blue]
> I think the Standard's use of "representation " in describing
> the shift operators is just for convenience of exposition, and
> does not refer to the "representation " as described in 6.2.6.[/color]

I see no inconsistency in assuming that it does.
[color=blue]
> Note that in addition to describing the shift result in terms
> of bit positions, the Standard also describes it in purely
> arithmetic form, as multiplication or division by an integer
> power of two -- this latter part only makes sense when applied
> to the value, not the representation, of the shifted quantity.[/color]

Absolutely. The standard defines the shift in terms of representation.
Under the conditions this implies a well-defined numerical result it
specifies that as well.

Lawrence

[Tim Rentsch]

Re: Arithmetic shift operation in C

Lawrence Kirby <lknews@netacti ve.co.uk> writes:
[color=blue]
> On Thu, 16 Jun 2005 10:51:50 -0700, Tim Rentsch wrote:
>
> ...
>[color=green]
> > Are we reading different documents? The description I read of the
> > "Bitwise shift operators" (ISO/IEC 9899:1999 (E), section 6.5.7) talks
> > only about values, not about representations .[/color]
>
> It talks abouyt thinks like "bit positions" which is a description of
> representation rather than value.[/color]

It seems clear from context in the rest of the paragraph that these
phrases refer to bit positions of the value, not bit positions of the
representation. Yes? If it isn't clear then perhaps the language
should be changed to reflect that, because it seems obvious that this
interpretation is what was intended.

6.5.7

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 a
nonnegative value, and E1 x 2**E2 is representable in the result type,
then that is the resulting value; otherwise, the behavior is
undefined.

5 The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1
has an unsigned type or if E1 has a signed type and a nonnegative
value, the value of the result is the integral part of the quotient of
E1 / 2**E2. If E1 has signed type and a negative value, the resulting
value is implementation-defined.

[Jean-Claude Arbaut]

Re: Arithmetic shift operation in C




Le 16/06/2005 20:11, dans pan.2005.06.16. 18.12.29.703000 @netactive.co.u k,
« Lawrence Kirby » <lknews@netacti ve.co.uk> a écrit :
[color=blue]
> On Thu, 16 Jun 2005 12:41:04 +0200, Jean-Claude Arbaut wrote:
>
> ...
>
>[color=green]
>> On modern x86, gcc can eliminate the jump and use a conditionnal move:
>>
>> movl 4(%esp), %eax
>> leal 3(%eax), %edx
>> cmpl $-1, %eax
>> cmovle %edx, %eax
>> sarl $2, %eax
>> ret
>>
>> But that has nothing to do with the OP, it's just an optimization trick.[/color]
>
> The point remains the same, the code demonstrates a difference between
> division and arithmetic shifting.[/color]


Yes, of course. I would not try to beat you on your territory ;-)

[Richard Bos]

Re: Arithmetic shift operation in C

Eric Sosman <eric.sosman@su n.com> wrote:
[color=blue]
> Lawrence Kirby wrote:[color=green]
> > On Thu, 16 Jun 2005 07:15:58 +0000, Richard Bos wrote:
> >[color=darkred]
> >>CBFalconer <cbfalconer@yah oo.com> wrote:
> >>
> >>>There is a lot of misinformation in the replies you have received.
> >>>Shift operations in C are only portable, and properly defined, on
> >>>unsigned objects.
> >>
> >>This is not true. They are only portable, and properly defined, on
> >>non-negative values. C never shifts objects, it shifts values;[/color]
> >
> > That's tricky, a shift works at the representation level, and in addition
> > the standard defines the effect on values in some circumstances.[/color]
>
> The Standard describes the shift operators in terms of
> a binary representation, but I think R.B. is right: they
> operate on values, not on "the" representations .[/color]

That's a non-issue, really, and not what I wrote. Since the
representation of non-negative integers is pretty well fixed, at least
in the way that the definition of the << and >> operators do, you could
say that they work on representations as much as on values.
However, what Mr. Kirby wrote, and what I objected to, is that shifts
operate on _objects_. They don't do that; which can be proved quite
simply by noting that you can shift constants.

Richard

[Lawrence Kirby]

Re: Arithmetic shift operation in C

On Fri, 17 Jun 2005 09:18:05 +0000, Richard Bos wrote:

....
[color=blue]
> That's a non-issue, really, and not what I wrote. Since the
> representation of non-negative integers is pretty well fixed, at least
> in the way that the definition of the << and >> operators do, you could
> say that they work on representations as much as on values.
> However, what Mr. Kirby wrote, and what I objected to, is that shifts
> operate on _objects_. They don't do that; which can be proved quite
> simply by noting that you can shift constants.[/color]

I'm not saying shifts work on objects (I don't think I did but if so that
was a mistake), I'm saying that they work at a representation level.

Lawrence

[Richard Bos]

Re: Arithmetic shift operation in C

Lawrence Kirby <lknews@netacti ve.co.uk> wrote:
[color=blue]
> On Fri, 17 Jun 2005 09:18:05 +0000, Richard Bos wrote:
>[color=green]
> > However, what Mr. Kirby wrote, and what I objected to, is that shifts
> > operate on _objects_.[/color]
>
> I'm not saying shifts work on objects (I don't think I did but if so that
> was a mistake), I'm saying that they work at a representation level.[/color]

True. It wasn't you who brought up objects, it was Mr. Falconer. My
excuses.

Richard

[Chris Torek]

Re: Arithmetic shift operation in C

>On Thu, 16 Jun 2005 10:51:50 -0700, Tim Rentsch wrote:[color=blue][color=green]
>> Are we reading different documents? The description I read of the
>> "Bitwise shift operators" (ISO/IEC 9899:1999 (E), section 6.5.7) talks
>> only about values, not about representations .[/color][/color]

In article <pan.2005.06.16 .18.46.53.98500 0@netactive.co. uk>
Lawrence Kirby <lknews@netacti ve.co.uk> wrote:[color=blue]
>It talks abouyt thinks like "bit positions" which is a description of
>representati on rather than value.[/color]

I think perhaps the confusion comes in because this is a description
of "a" representation, and not necessarily "the" representation.
That is, the machine could have obnoxious padding bits in the way;
but if so, they do not participate in the value-bit-shifting.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[CBFalconer]

Re: Arithmetic shift operation in C

Richard Bos wrote:[color=blue]
> Lawrence Kirby <lknews@netacti ve.co.uk> wrote:[color=green]
>> On Fri, 17 Jun 2005 09:18:05 +0000, Richard Bos wrote:
>>[color=darkred]
>>> However, what Mr. Kirby wrote, and what I objected to, is that
>>> shifts operate on _objects_.[/color]
>>
>> I'm not saying shifts work on objects (I don't think I did but
>> if so that was a mistake), I'm saying that they work at a
>> representation level.[/color]
>
> True. It wasn't you who brought up objects, it was Mr. Falconer.
> My excuses.[/color]

Whatever you're accusing me of, I didn't do it.

--
Some informative links:
news:news.annou nce.newusers

http://www.geocities.com/nnqweb/

http://www.catb.org/~esr/faqs/smart-questions.html

http://www.caliburn.nl/topposting.html

http://www.netmeister.org/news/learn2quote.html

[Eric Sosman]

Re: Arithmetic shift operation in C

CBFalconer wrote:[color=blue]
>
> Whatever you're accusing me of, I didn't do it.[/color]

"I wasn't there."
-- Pooh-Bah, "The Mikado"

--
Eric Sosman
esosman@acm-dot-org.invalid

[Richard Bos]

Re: Arithmetic shift operation in C

In comp.lang.c you wrote:
[color=blue]
> Richard Bos wrote:[color=green]
> > Lawrence Kirby <lknews@netacti ve.co.uk> wrote:[color=darkred]
> >> On Fri, 17 Jun 2005 09:18:05 +0000, Richard Bos wrote:
> >>
> >>> However, what Mr. Kirby wrote, and what I objected to, is that
> >>> shifts operate on _objects_.
> >>
> >> I'm not saying shifts work on objects (I don't think I did but
> >> if so that was a mistake), I'm saying that they work at a
> >> representation level.[/color]
> >
> > True. It wasn't you who brought up objects, it was Mr. Falconer.
> > My excuses.[/color]
>
> Whatever you're accusing me of, I didn't do it.[/color]

I'm accusing you of writing this:
[color=blue]
> Shift operations in C are only portable, and properly defined, on
> unsigned objects.[/color]

and you did (<42B05C25.F796 5B55@yahoo.com> ).

I'm quite willing to accept your innocence in general, of course, you
sweet, unsuspecting darling, you :-P.

Richard