Bitwise/Arithmetic shift.
TimE
I understand the concept of bitwise shift. Could anyone tell
me the difference between bitwise shift ans arithmetic shift
Thanks.
Mark A. Odell
@nntp.tfvs.tp.edu.tw>:
>Hi,
>
>I understand the concept of bitwise shift. Could anyone tell
>me the difference between bitwise shift ans arithmetic shift
I don't think there is a difference. In C you can do a <<= 1; or a >>= 1; I
know of no other way to shift bits. Well maybe you could multiply or divide
by two. Do you have an example?
--
Warmest regards.
Optimize only if it runs too slowly or does not fit, spaces instead of tabs.
Mathew Hendry
: I understand the concept of bitwise shift. Could anyone tell
: me the difference between bitwise shift ans arithmetic shift
Arithmetic shift is a type of bitwise shift that preserves the sign of
the number. For example
int n = -1;
n <<= 1;
will result in n == -2 if the shift is arithmetic. (It might not be:
your compiler documentation should tell you what results to expect
when you shift negative numbers).
-- Mat.
Mal Kay
The C language does not refer to arithmetic shifts but only
bitwise shifts.
It other contexts shifts are often classified as logical or arithmetic;
and detailed definitions may very from one processor to another or
according to the ideas of the author.
The distinction is often confined to right shifts for which the logical
shift moves a zero into the most significant bit while in an arithmetic
shift the sign bit is duplicated so that the sign of a signed number
remains unchanged.
The C standard effectively defines bitwise shifts on unsigned types as a
logical shift, and leaves the type of shift for negative signed types as
implimentation dependent.
Malcolm Kay
Dan Pop
>I understand the concept of bitwise shift. Could anyone tell
>me the difference between bitwise shift ans arithmetic shift
The proper term is logical shift.
A logical right shift will insert zeroes in the "freed" bit positions.
An arithmetic right shift will replicate the sign bit in the "freed" bit
positions.
There is only one flavour of left shift, which inserts zeroes in the
"freed" bit positions.
When the LHS operand of the right shift operator is unsigned, a logical
shift will be performed. When it is signed, it's up to the implementation
to choose (and document) which flavour of shift will be performed.
Dan
--
Dan Pop
CERN, IT Division
Email: Dan...@cern.ch
Mail: CERN - IT, Bat. 31 1-014, CH-1211 Geneve 23, Switzerland
Kevin Solomon
When performing a logical right shift of a signed long after first masking
high order bytes I've seen the sign bit propagated across the freed bits .
This undoubtedly does not occur with every compiler but, the programmer
should be aware that this can happen. Here is an example of what I mean.
Both mask and myfield are signed long.
mask = myfield & 0xFF000000;
mask = mask >> 24;
/* At this point if you displayed the value of mask in memory you will
sometimes get 0xFFFFFFyy . You then ensure that the propagated values are
removed by reapplying the mask */
mask = mask & 0xFF;
myfield = mask;
/* You are then assurred of having the value 0x000000yy */
glen herrmannsfeldt
>"TimE" <timw...@hotmail.nospam.com> writes:
>>I understand the concept of bitwise shift. Could anyone tell
>>me the difference between bitwise shift ans arithmetic shift
>The proper term is logical shift.
(snip)
>There is only one flavour of left shift, which inserts zeroes in the
>"freed" bit positions.
IBM S/370 and S/390 have both arithmetic and logical left shift.
They shift only the low 31 or 63 bits and leave the sign bit unchanged.
Overflow will be signaled in the condition code, and if enable a
fixed point overflow interrupt will occur. I don't know if C
compilers generate this instruction for signed integer shifts.
See:
http://www.s390.ibm.com:80/bookmgr-cgi/bookmgr.exe/BOOKS/DZ9AR006/7%2e5%2e77
>When the LHS operand of the right shift operator is unsigned, a logical
>shift will be performed. When it is signed, it's up to the implementation
>to choose (and document) which flavour of shift will be performed.
>Dan
-- glen
CBFalconer
>
> In <3ab05...@nntp.tfvs.tp.edu.tw> "TimE" <timw...@hotmail.nospam.com> writes:
>
> >I understand the concept of bitwise shift. Could anyone tell
> >me the difference between bitwise shift ans arithmetic shift
>
> The proper term is logical shift.
>
> A logical right shift will insert zeroes in the "freed" bit positions.
> An arithmetic right shift will replicate the sign bit in the "freed" bit
> positions.
>
> There is only one flavour of left shift, which inserts zeroes in the
> "freed" bit positions.
>
> When the LHS operand of the right shift operator is unsigned, a logical
> shift will be performed. When it is signed, it's up to the implementation
> to choose (and document) which flavour of shift will be performed.
To my mind a good quality of implementation issue. R shifts of
signed integers should be arithmetic, of unsigned should be
logical. Note that this does NOT allow division by 2 to be
generally implemented by a shift.
All machines of interest known to me have both forms of machine
instructions, so it should be feasible everywhere. I suspect the
standard does not specify this because it would break many
existing systems.
--
Chuck F (cbfal...@my-deja.com) (cbfal...@XXXXworldnet.att.net)
http://www.qwikpages.com/backstreets/cbfalconer
(Remove "NOSPAM." from reply address. my-deja works unmodified)
mailto:u...@ftc.gov (for spambots to harvest)
Joe Maun
>
> In <3ab05...@nntp.tfvs.tp.edu.tw> "TimE" <timw...@hotmail.nospam.com> writes:
>
> >I understand the concept of bitwise shift. Could anyone tell
> >me the difference between bitwise shift ans arithmetic shift
>
> The proper term is logical shift.
>
> A logical right shift will insert zeroes in the "freed" bit positions.
> An arithmetic right shift will replicate the sign bit in the "freed" bit
> positions.
>
> There is only one flavour of left shift, which inserts zeroes in the
> "freed" bit positions.
>
> When the LHS operand of the right shift operator is unsigned, a logical
> shift will be performed. When it is signed, it's up to the implementation
> to choose (and document) which flavour of shift will be performed.
It doesn't have to choose between these two shifts, however. If the
value is negative, it can make up an as of yet unheard shift, which
always results in the value of 0x0FAB, for example. (As long as it is
documented, of course.)
--
Joe Maun
Montreal, QC
Canada
Dan Pop
>Dan Pop wrote:
>>
>> In <3ab05...@nntp.tfvs.tp.edu.tw> "TimE" <timw...@hotmail.nospam.com> writes:
>>
>> >I understand the concept of bitwise shift. Could anyone tell
>> >me the difference between bitwise shift ans arithmetic shift
>>
>> The proper term is logical shift.
>>
>> A logical right shift will insert zeroes in the "freed" bit positions.
>> An arithmetic right shift will replicate the sign bit in the "freed" bit
>> positions.
>>
>> There is only one flavour of left shift, which inserts zeroes in the
>> "freed" bit positions.
>>
>> When the LHS operand of the right shift operator is unsigned, a logical
>> shift will be performed. When it is signed, it's up to the implementation
>> to choose (and document) which flavour of shift will be performed.
>
>It doesn't have to choose between these two shifts, however.
Where did I say that it has to choose between *two* shifts?
Joe Maun
>
> In <3AB25409...@yahoo.com> Joe Maun <repl...@yahoo.com> writes:
>
> >Dan Pop wrote:
> >>
> >> In <3ab05...@nntp.tfvs.tp.edu.tw> "TimE" <timw...@hotmail.nospam.com> writes:
> >>
> >> >I understand the concept of bitwise shift. Could anyone tell
> >> >me the difference between bitwise shift ans arithmetic shift
> >>
> >> The proper term is logical shift.
> >>
> >> A logical right shift will insert zeroes in the "freed" bit positions.
> >> An arithmetic right shift will replicate the sign bit in the "freed" bit
> >> positions.
> >>
> >> There is only one flavour of left shift, which inserts zeroes in the
> >> "freed" bit positions.
> >>
> >> When the LHS operand of the right shift operator is unsigned, a logical
> >> shift will be performed. When it is signed, it's up to the implementation
> >> to choose (and document) which flavour of shift will be performed.
> >
> >It doesn't have to choose between these two shifts, however.
>
> Where did I say that it has to choose between *two* shifts?
Where did I say that you said it has to choose between two shifts?
Lawrence Kirby
...
>It doesn't have to choose between these two shifts, however. If the
>value is negative, it can make up an as of yet unheard shift, which
>always results in the value of 0x0FAB, for example. (As long as it is
>documented, of course.)
C99 has messed around with left shifts for signed integer types. It says
that the behaviour is undefined if the value to be shifted is negative
or if the value is positive and the shift would cause overflow.
For right shifting C99 is the same as C90 i.e. right shifting a negative
value gives an implementation-defined result. However in both standard
the result us subject to the stipulation that "The result of E1 >> E2
is E1 right-shifted E2 bit positions." Clearly producing a value of
0x0FAB in every case is not consistent with this stipulation.
--
-----------------------------------------
Lawrence Kirby | fr...@genesis.demon.co.uk
Wilts, England | 7073...@compuserve.com
-----------------------------------------
pete
> > Where did I say that it has to choose between *two* shifts?
>
> Where did I say that you said it has to choose between two shifts?
/* BEGIN, one_more.c */
#include <stdio.h>
#define ONE_MORE 3
int main(void)
{
unsigned char x, y, *Where = "Where did I say that ",
*You = "you said that ", *I = "I said that ",
*Choose = "it has to choose between two shifts ?\n\n",
*string[2];
for(y = ONE_MORE; y; y--){
for(x = y ; x; x--)
printf(">");
printf(Where);
x = ONE_MORE - y;
string[x & 1] = I;
string[!(x & 1)] = You;
while(x--)
printf(string[x & 1]);
printf(Choose);
}
return 0;
}
/* END, one_more.c */
--
pete
Dan Pop
>In article <3AB25409...@yahoo.com> repl...@yahoo.com "Joe Maun" writes:
>
>For right shifting C99 is the same as C90 i.e. right shifting a negative
>value gives an implementation-defined result. However in both standard
>the result us subject to the stipulation that "The result of E1 >> E2
>is E1 right-shifted E2 bit positions." Clearly producing a value of
>0x0FAB in every case is not consistent with this stipulation.
OTOH, filling the freed bit positions with a random bit pattern is.
Dik T. Winter
...
> To my mind a good quality of implementation issue. R shifts of
> signed integers should be arithmetic, of unsigned should be
> logical. Note that this does NOT allow division by 2 to be
> generally implemented by a shift.
>
> All machines of interest known to me have both forms of machine
> instructions, so it should be feasible everywhere. I suspect the
> standard does not specify this because it would break many
> existing systems.
There are machines that do not have an arithmetic shift (think Cray).
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
CBFalconer
>
> In article <3AB00FE6...@my-deja.com> cbfal...@worldnet.att.net writes:
> ...
> > To my mind a good quality of implementation issue. R shifts of
> > signed integers should be arithmetic, of unsigned should be
> > logical. Note that this does NOT allow division by 2 to be
> > generally implemented by a shift.
> >
> > All machines of interest known to me have both forms of machine
> > instructions, so it should be feasible everywhere. I suspect the
> > standard does not specify this because it would break many
> > existing systems.
>
> There are machines that do not have an arithmetic shift (think Cray).
If my premises are wrong then the conclusions are likewise :-) I
have always thought that machines should provide both arith and
logical shifts, left and right, with ASL capable of generating
overflow traps. All versions should shift out into a carry bit,
and for logical shifts both through and around a carry bit. This
is not the first time the world has disagreed with me :-)
Chris Torek
CBFalconer <cbfal...@worldnet.att.net> writes:
>If my premises are wrong then the conclusions are likewise :-) I
>have always thought that machines should provide both arith and
>logical shifts, left and right, with ASL capable of generating
>overflow traps. All versions should shift out into a carry bit,
>and for logical shifts both through and around a carry bit. This
>is not the first time the world has disagreed with me :-)
There are machines with no carry bits, too (e.g., MIPS processors).
I sort of like the idea of designating any register as a "condition
codes" register, but for CPU design reasons, it tends to be faster
to have dedicated "cc" registers (SPARC's %icc/%xcc; IA64 predicate
registers?), or no cc register at all (MIPS).
One of the good things about C is that it insulates you from this
level of detail. This is also one of the bad things about C. :-)
--
In-Real-Life: Chris Torek, Berkeley Software Design Inc
El Cerrito, CA, USA Domain: to...@bsdi.com +1 510 234 3167
http://claw.bsdi.com/torek/ (not always up) I report spam to abuse@.
Note: PacBell news service is rotten
Dik T. Winter
> "Dik T. Winter" wrote:
...
> > There are machines that do not have an arithmetic shift (think Cray).
>
> If my premises are wrong then the conclusions are likewise :-) I
> have always thought that machines should provide both arith and
> logical shifts, left and right, with ASL capable of generating
> overflow traps. All versions should shift out into a carry bit,
> and for logical shifts both through and around a carry bit. This
> is not the first time the world has disagreed with me :-)
Well, as the Cray is not able to generate an integer overflow trap, and
does not have status bits either, indeed, yes. BTW, the Cray is not
the only processor without status bits, there are quite a few modern
machines without them (think MIPS).
Arithmetic shift is a bit bothersome on the Cray because it is not
entirely clear how many bits should be used in the shift. In most
operations an integer is 48 bits plus a sign bit, in other operations
it is 63 bits plus a sign bit. And again it can also be 24 bits plus
a sign bit.
Lawrence Kirby
>In <984786...@genesis.demon.co.uk> fr...@genesis.demon.co.uk (Lawrence Kirby)
> writes:
>
>>In article <3AB25409...@yahoo.com> repl...@yahoo.com "Joe Maun" writes:
>>
>>For right shifting C99 is the same as C90 i.e. right shifting a negative
>>value gives an implementation-defined result. However in both standard
>>the result us subject to the stipulation that "The result of E1 >> E2
>>is E1 right-shifted E2 bit positions." Clearly producing a value of
>>0x0FAB in every case is not consistent with this stipulation.
>
>OTOH, filling the freed bit positions with a random bit pattern is.
Yes, there are certainly no stipulations about what bit values are
shifted in from the top in this case.
CBFalconer
>
> In <984786...@genesis.demon.co.uk> fr...@genesis.demon.co.uk (Lawrence Kirby) writes:
>
> >In article <3AB25409...@yahoo.com> repl...@yahoo.com "Joe Maun" writes:
> >
> >For right shifting C99 is the same as C90 i.e. right shifting a negative
> >value gives an implementation-defined result. However in both standard
> >the result us subject to the stipulation that "The result of E1 >> E2
> >is E1 right-shifted E2 bit positions." Clearly producing a value of
> >0x0FAB in every case is not consistent with this stipulation.
>
> OTOH, filling the freed bit positions with a random bit pattern is.
Are you sure your line of work is not creating ultra fine print
segments for insurance policies? :-)
Joe Maun
>
> In article <3AB25409...@yahoo.com> repl...@yahoo.com "Joe Maun" writes:
>
> ...
>
> >It doesn't have to choose between these two shifts, however. If the
> >value is negative, it can make up an as of yet unheard shift, which
> >always results in the value of 0x0FAB, for example. (As long as it is
> >documented, of course.)
>
[...]
> For right shifting C99 is the same as C90 i.e. right shifting a negative
> value gives an implementation-defined result. However in both standard
> the result us subject to the stipulation that "The result of E1 >> E2
> is E1 right-shifted E2 bit positions." Clearly producing a value of
> 0x0FAB in every case is not consistent with this stipulation.
Quite correct. After rereading "Bitwise shift operators" it seems clear
that the sentence "If E1 has a signed type and a negative value, the
resulting value is implementation-defined" does /not/ absolve the
implementation of the requirement that "The result of E1 >> E2 is E1
right-shifted E2 bit positions" as I had previously thought. Thank you.
The freed bit positions can still be filled any way the implementation
likes, of course.
(I'm not sure it can actually be "random", as Dan has suggested. Does
"the result is random" satisfy the requirement that "[...]
implementation documents how the choice is made"? It sounds much like
"how the choice is made is a trade secret" to me, which certainly
doesn't satisfy that requirement. Unless the documentation includes the
source of the prng and the seed value (in which case it is no longer
"random" in a real sense). Or perhaps even if it documents an external
source from where it gets random bits? )
Dan Pop
>(I'm not sure it can actually be "random", as Dan has suggested. Does
>"the result is random" satisfy the requirement that "[...]
>implementation documents how the choice is made"?
Where does the standard forbid a random choice for implementation-defined
behaviour (as long as the implementation documents that the choice is
random)?
>It sounds much like
>"how the choice is made is a trade secret" to me, which certainly
>doesn't satisfy that requirement. Unless the documentation includes the
>source of the prng and the seed value (in which case it is no longer
>"random" in a real sense). Or perhaps even if it documents an external
>source from where it gets random bits? )
What if the "random" bits are the least significant bits of an internal
cycle counter?
Joe Maun
>
> In <3AB41CBD...@yahoo.com> Joe Maun <repl...@yahoo.com> writes:
>
> >(I'm not sure it can actually be "random", as Dan has suggested. Does
> >"the result is random" satisfy the requirement that "[...]
> >implementation documents how the choice is made"?
>
> Where does the standard forbid a random choice for implementation-defined
> behaviour (as long as the implementation documents that the choice is
> random)?
It depends on what you mean by "random". If the documentation simply
says "the value will be random" then I don't think that counts as
documenting "how the choice is made". Even if it says "the choice is
made based on the high order bits of a prng" I still don't think that
really tells us "how the choice is made", unless it also includes the
algorithm, as I noted.
[...]
> >"random" in a real sense). Or perhaps even if it documents an external
> >source from where it gets random bits? )
>
> What if the "random" bits are the least significant bits of an internal
> cycle counter?
If that counter is internal to the program (it counts the cycles used by
this program), I wouldn't call that "random". I would simply call it
"the bits of the internal cycle counter". When you said "random", I was
thinking in terms of unpredictable (in terms of this program)
randomness, although perhaps even an internal cycle counter can be seen
as "random" in some contexts.
Dan Pop
>Dan Pop wrote:
>>
>> In <3AB41CBD...@yahoo.com> Joe Maun <repl...@yahoo.com> writes:
>>
>> >(I'm not sure it can actually be "random", as Dan has suggested. Does
>> >"the result is random" satisfy the requirement that "[...]
>> >implementation documents how the choice is made"?
>>
>> Where does the standard forbid a random choice for implementation-defined
>> behaviour (as long as the implementation documents that the choice is
>> random)?
>
>It depends on what you mean by "random". If the documentation simply
>says "the value will be random" then I don't think that counts as
>documenting "how the choice is made".
You are entitled to your opinions, of course. The question is whether
a random choice is allowed by the standard. As far as I can tell, there
is nothing in the standard ruling out this possibility, therefore it is
allowed.
>> >"random" in a real sense). Or perhaps even if it documents an external
>> >source from where it gets random bits? )
>>
>> What if the "random" bits are the least significant bits of an internal
>> cycle counter?
>
>If that counter is internal to the program (it counts the cycles used by
>this program), I wouldn't call that "random".
I was thinking about a cycle counter that is internal to the CPU
(some processors do have such things) and whose value may not even be
available to the C program.
Joe Maun
>
> In <3AB51088...@yahoo.com> Joe Maun <repl...@yahoo.com> writes:
>
> >Dan Pop wrote:
> >>
> >> In <3AB41CBD...@yahoo.com> Joe Maun <repl...@yahoo.com> writes:
[...]
> >> >"random" in a real sense). Or perhaps even if it documents an external
> >> >source from where it gets random bits? )
> >>
> >> What if the "random" bits are the least significant bits of an internal
> >> cycle counter?
> >
> >If that counter is internal to the program (it counts the cycles used by
> >this program), I wouldn't call that "random".
>
> I was thinking about a cycle counter that is internal to the CPU
> (some processors do have such things) and whose value may not even be
> available to the C program.
That is what I meant by "external" (external to the program, not the
hardware).
Lawrence Kirby
>In <3AB51088...@yahoo.com> Joe Maun <repl...@yahoo.com> writes:
>
>>Dan Pop wrote:
>>>
>>> In <3AB41CBD...@yahoo.com> Joe Maun <repl...@yahoo.com> writes:
>>>
>>> >(I'm not sure it can actually be "random", as Dan has suggested. Does
>>> >"the result is random" satisfy the requirement that "[...]
>>> >implementation documents how the choice is made"?
>>>
>>> Where does the standard forbid a random choice for implementation-defined
>>> behaviour (as long as the implementation documents that the choice is
>>> random)?
>>
>>It depends on what you mean by "random". If the documentation simply
>>says "the value will be random" then I don't think that counts as
>>documenting "how the choice is made".
Although that is a lot more informative than some of the descriptions
that are provided for implementation-defined behaviour. Unfortunately
there is no specification of documentation quality in the standard.
I did point this out in the run-up to C99 but for some reason nobody
showed any enthusiasm about opening that can of worms. :-)
glen herrmannsfeldt
>In <3AB41CBD...@yahoo.com> Joe Maun <repl...@yahoo.com> writes:
>>(I'm not sure it can actually be "random", as Dan has suggested. Does
>>"the result is random" satisfy the requirement that "[...]
>>implementation documents how the choice is made"?
>Where does the standard forbid a random choice for implementation-defined
>behaviour (as long as the implementation documents that the choice is
>random)?
(snip)
>What if the "random" bits are the least significant bits of an internal
>cycle counter?
How about the bits remaining in another register. For example, a machine
with 64 bit registers and 32 bit int could shift in those extra bits.
-- glen