Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > left shifts (rationale question)

Reply
Thread Tools

left shifts (rationale question)

 
 
Christopher Layne
Guest
Posts: n/a
 
      02-03-2007
So I recently ran into a situation where I invoked UB without specifically
knowing I did it. Yes, human, I know.

What exactly is/was the rationale for not allowing shifts to be the same width
of the datatype one is shifting? Also, for most common platforms (oh,
alright, x86), it's okay to do at the assembly level, isn't it? (provided the
opcodes allow it, I guess that's my question as well).
 
Reply With Quote
 
 
 
 
=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=
Guest
Posts: n/a
 
      02-03-2007
Christopher Layne wrote:
> So I recently ran into a situation where I invoked UB without specifically
> knowing I did it. Yes, human, I know.
>
> What exactly is/was the rationale for not allowing shifts to be the same width
> of the datatype one is shifting? Also, for most common platforms (oh,
> alright, x86), it's okay to do at the assembly level, isn't it? (provided the
> opcodes allow it, I guess that's my question as well).


No, it's not okay for some common platforms, such as x86, and that's
why it's not allowed.

 
Reply With Quote
 
 
 
 
Walter Roberson
Guest
Posts: n/a
 
      02-03-2007
In article <(E-Mail Removed)>,
Christopher Layne <(E-Mail Removed)> wrote:
>What exactly is/was the rationale for not allowing shifts to be the same width
>of the datatype one is shifting?


We went through this pretty recently, last week or so:

There are a number of common processors where the upper bits of the
shift count are ignored, so using a shift count equal to the word
width is equivilent to using a shift count of 0 on those processors.

If things were otherwise, it could take a long time for a processor
to finish shifting by 0x7fffffff bits...
--
Prototypes are supertypes of their clones. -- maplesoft
 
Reply With Quote
 
santosh
Guest
Posts: n/a
 
      02-03-2007
Christopher Layne wrote:
> So I recently ran into a situation where I invoked UB without specifically
> knowing I did it. Yes, human, I know.
>
> What exactly is/was the rationale for not allowing shifts to be the same width
> of the datatype one is shifting? Also, for most common platforms (oh,
> alright, x86), it's okay to do at the assembly level, isn't it? (provided the
> opcodes allow it, I guess that's my question as well).


Particularly the 32 bit x86 processors ignore the upper 27 bits during
shift operations. Only the lower 5 bits are taken into consideration
since the maximum sane value for shifting a 32 bit value is 31.

 
Reply With Quote
 
Chris Dollin
Guest
Posts: n/a
 
      02-05-2007
santosh wrote:

> Christopher Layne wrote:
>> So I recently ran into a situation where I invoked UB without specifically
>> knowing I did it. Yes, human, I know.
>>
>> What exactly is/was the rationale for not allowing shifts to be the same width
>> of the datatype one is shifting? Also, for most common platforms (oh,
>> alright, x86), it's okay to do at the assembly level, isn't it? (provided the
>> opcodes allow it, I guess that's my question as well).

>
> Particularly the 32 bit x86 processors ignore the upper 27 bits during
> shift operations. Only the lower 5 bits are taken into consideration
> since the maximum sane value for shifting a 32 bit value is 31.


Um ... I dispute the "sane" bit. It's perfectly /sane/ to shift a 32-bit
quantity right by 32, or 61, or 9763; one would [1] expect to get 0.

It's a shame that processors don't respect that, but I assume -- my stars,
I really do hope strongly -- that there are good hardware reasons why doing
the right thing would be too expensive.

Given the existence of such hardware, and C's design goals, C's definition
for shifting seems like the only available answer. Deep gloom.

[1] "one'd"?

--
Chris "electric hedgehog" Dollin
"It took a very long time, much longer than the most generous estimates."
- James White, /Sector General/

 
Reply With Quote
 
santosh
Guest
Posts: n/a
 
      02-05-2007
Chris Dollin wrote:
> santosh wrote:
>
> > Christopher Layne wrote:
> >> So I recently ran into a situation where I invoked UB without specifically
> >> knowing I did it. Yes, human, I know.
> >>
> >> What exactly is/was the rationale for not allowing shifts to be the same width
> >> of the datatype one is shifting? Also, for most common platforms (oh,
> >> alright, x86), it's okay to do at the assembly level, isn't it? (provided the
> >> opcodes allow it, I guess that's my question as well).

> >
> > Particularly the 32 bit x86 processors ignore the upper 27 bits during
> > shift operations. Only the lower 5 bits are taken into consideration
> > since the maximum sane value for shifting a 32 bit value is 31.

>
> Um ... I dispute the "sane" bit. It's perfectly /sane/ to shift a 32-bit
> quantity right by 32, or 61, or 9763; one would [1] expect to get 0.


I can't think of a realistic reason to shift a N bit value by more
than N bits. In fact, from the point of view of standard C, that would
be N - 1 bits. Maybe it makes sense in some exotic implementation, but
I struggle to imagine how.

> It's a shame that processors don't respect that, but I assume -- my stars,
> I really do hope strongly -- that there are good hardware reasons why doing
> the right thing would be too expensive.


I don't know much about hardware, but Walter Roberson did mention that
ridiculously large shift values like 0x7fffffff would take a long time
to complete, and achieve nothing.

 
Reply With Quote
 
Stuart
Guest
Posts: n/a
 
      02-05-2007
"santosh" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...

> I can't think of a realistic reason to shift a N bit value by more
> than N bits. In fact, from the point of view of standard C, that would
> be N - 1 bits. Maybe it makes sense in some exotic implementation, but
> I struggle to imagine how.


In low-level (machine) code it can be a useful way of setting a whole
register to the same as the sign bit without making a branch. (Arithmetic
right shifting usually propagates the sign bit - so you get 0 for positive
starting values and all '1's [aka -1] for a negative starting value).

This could of course be directly incorporated into other bit-twiddling logic
expressions!

> I don't know much about hardware, but Walter Roberson did mention that
> ridiculously large shift values like 0x7fffffff would take a long time
> to complete, and achieve nothing.


Perhaps on some [generally] older technologies; many current generation
processors have barrel-shifters which means it all takes 1-clock no matter
how many places you are shifting.

HTH
--
Stuart


 
Reply With Quote
 
Chris Dollin
Guest
Posts: n/a
 
      02-05-2007
santosh wrote:

> Chris Dollin wrote:
>> santosh wrote:
>>
>> > Christopher Layne wrote:
>> >> So I recently ran into a situation where I invoked UB without specifically
>> >> knowing I did it. Yes, human, I know.
>> >>
>> >> What exactly is/was the rationale for not allowing shifts to be the same width
>> >> of the datatype one is shifting? Also, for most common platforms (oh,
>> >> alright, x86), it's okay to do at the assembly level, isn't it? (provided the
>> >> opcodes allow it, I guess that's my question as well).
>> >
>> > Particularly the 32 bit x86 processors ignore the upper 27 bits during
>> > shift operations. Only the lower 5 bits are taken into consideration
>> > since the maximum sane value for shifting a 32 bit value is 31.

>>
>> Um ... I dispute the "sane" bit. It's perfectly /sane/ to shift a 32-bit
>> quantity right by 32, or 61, or 9763; one would [1] expect to get 0.

>
> I can't think of a realistic reason to shift a N bit value by more
> than N bits.


Correctness.

Edge cases (where a shift by N+1 arises as a natural conseqence of
the algorithm being used).

Interpreters (where the shift count isn't known until run-time and
the language requires the result to be zero).

>> It's a shame that processors don't respect that, but I assume -- my stars,
>> I really do hope strongly -- that there are good hardware reasons why doing
>> the right thing would be too expensive.

>
> I don't know much about hardware, but Walter Roberson did mention that
> ridiculously large shift values like 0x7fffffff would take a long time
> to complete, and achieve nothing.


If the shift count has bits set outside the non-trivial shift range, the
result is 0. So I can imagine or-gating all those bits together and using
that bit to control whether the shifter shifts or delivers 0. Of course,
since I'm not a hardware person, I can imagine that this is cheap; but
perhaps it isn't.

--
Chris "electric hedgehog" Dollin
A rock is not a fact. A rock is a rock.

 
Reply With Quote
 
=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=
Guest
Posts: n/a
 
      02-05-2007
Stuart wrote:
> "santosh" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) oups.com...
>
> > I can't think of a realistic reason to shift a N bit value by more
> > than N bits. In fact, from the point of view of standard C, that would
> > be N - 1 bits. Maybe it makes sense in some exotic implementation, but
> > I struggle to imagine how.

>
> In low-level (machine) code it can be a useful way of setting a whole
> register to the same as the sign bit without making a branch. (Arithmetic
> right shifting usually propagates the sign bit - so you get 0 for positive
> starting values and all '1's [aka -1] for a negative starting value).


For that, you can right-shift by N-1 bits, can you not?

> This could of course be directly incorporated into other bit-twiddling logic
> expressions!
>
> > I don't know much about hardware, but Walter Roberson did mention that
> > ridiculously large shift values like 0x7fffffff would take a long time
> > to complete, and achieve nothing.

>
> Perhaps on some [generally] older technologies; many current generation
> processors have barrel-shifters which means it all takes 1-clock no matter
> how many places you are shifting.


Do modern x86 processors provide an instruction that shifts by the
specified amount without discarding any bits in the shift count?

 
Reply With Quote
 
Richard Tobin
Guest
Posts: n/a
 
      02-05-2007
In article <(E-Mail Removed) .com>,
santosh <(E-Mail Removed)> wrote:

>I can't think of a realistic reason to shift a N bit value by more
>than N bits.


A right shift of k bits can be interpreted as integer division by 2^k;
it's still correct when k is greater than the word size (returning
zero, or possibly -1 for signed shifts).

>I don't know much about hardware, but Walter Roberson did mention that
>ridiculously large shift values like 0x7fffffff would take a long time
>to complete, and achieve nothing.


That's a quality-of-implementation issue for the processor - it could
short-circuit shifts of >=N. But given that processors don't do this,
it would be expensive for C to implement.

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
 
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
Large table shifts to right while loading Richard HTML 1 12-18-2005 02:48 AM
python and bit shifts and byte order, oh my! Reid Nichol Python 11 09-11-2004 09:08 AM
Index Page Shifts Position HTML 3 08-08-2004 11:13 PM
Newbie -- bitwise shifts gbblob Python 2 02-04-2004 09:46 PM
Strangeness with shifts Glen Able C++ 2 11-24-2003 02:56 AM



Advertisments