Board index » delphi » Shifting and Rotating bits in Pascal

Shifting and Rotating bits in Pascal

Could someone explain how to shift (left and right) and rotate (left and
right) the bits in an integer in Pascal?

e-mail please.

Thanks,

-Dan

 

Re:Shifting and Rotating bits in Pascal


Quote
Daniel Jette wrote:
> Could someone explain how to shift (left and right) and rotate (left and
> right) the bits in an integer in Pascal?

Shifting right and left can be accomplished easily with the SHR and SHL
operators.  For example:

  num1 := a SHL b;

This will shift a left b times (multiply a by 2^b)

  num2 := c SHR d;

This will shift c right d times (divide c by 2^d)

Rotation is not directly implemented, but you can always use a little
assmebly.  For example:

function rotb_r (b, times : byte) : byte; assembler;

asm
  mov   al,[b]
  mov   cl,[times]
  ror   al,cl
end;

function rotb_l (b, times : byte) : byte; assembler;

asm
  mov   al,[b]
  mov   cl,[times]
  rol   al,cl
end;

Note:  you asked specifically about shifting the bits in an integer.
While you can specifically do that to the type "integer", keep in mind
that 15 bits are used for the value, and 1 bit is used as a sign.
Binary operations like this are usually less meaningful on signed
integer types, so it might make more sense in your code to use "word" in
place of integer.

Quote
> e-mail please.

Also posted, for the sake of the newsgroup.

Quote
> Thanks,

> -Dan

--
Scott Earnest                      | _,-""-_,-""-_,-""-_,-""-_,-""-_,-"
|
set...@ix.netcom.com (primary)     | We now return you to our regularly
|
siny...@{*word*104}space.org (alternate) | scheduled chaos and mayhem. . . .
|

Re:Shifting and Rotating bits in Pascal


Quote
Scott Earnest wrote:

> Daniel Jette wrote:

> > Could someone explain how to shift (left and right) and rotate (left and
> > right) the bits in an integer in Pascal?

[ snip snip snip ]

> Note:  you asked specifically about shifting the bits in an integer.
> While you can specifically do that to the type "integer", keep in mind
> that 15 bits are used for the value, and 1 bit is used as a sign.
> Binary operations like this are usually less meaningful on signed
> integer types, so it might make more sense in your code to use "word" in
> place of integer.

It isn't simply 1 bit for the sign, and 15 bits for the absolute calue,
it's stored in two's compliment notation that would get completely
screwed up when using negative numbers. As said before, you should use
"word" values.

Bye bye,
  Eilon Lipton /YOE
  AKA: Mad Man

Re:Shifting and Rotating bits in Pascal


In article <329C3C93.3...@ix.netcom.com>,
Scott Earnest  <set...@ix.netcom.com> wrote:

Quote

>Rotation is not directly implemented, but you can always use a little
>assmebly.  For example:

>function rotb_r (b, times : byte) : byte; assembler;

>asm
>  mov   al,[b]
>  mov   cl,[times]
>  ror   al,cl
>end;

No no. Those operations typically have to be fast. A procedure call
creates much overhead. One can just use:

var x:word;

begin
  x:=100;
  asm ror x,5 end;
  writeln(x);
end.

Quote

>function rotb_l (b, times : byte) : byte; assembler;

>asm
>  mov   al,[b]
>  mov   cl,[times]
>  rol   al,cl
>end;

>Note:  you asked specifically about shifting the bits in an integer.
>While you can specifically do that to the type "integer", keep in mind
>that 15 bits are used for the value, and 1 bit is used as a sign.
>Binary operations like this are usually less meaningful on signed
>integer types, so it might make more sense in your code to use "word" in
>place of integer.

There is arithmetic shift just because of the sign bit. (Note arithmetic
shift to the right by 1 is not same as division by 2, it is close though)

Osmo

Re:Shifting and Rotating bits in Pascal


Quote
Osmo Ronkanen wrote:

> In article <329C3C93.3...@ix.netcom.com>,
> Scott Earnest  <set...@ix.netcom.com> wrote:

> >Rotation is not directly implemented, but you can always use a little
> >assmebly.  For example:

> >function rotb_r (b, times : byte) : byte; assembler;

> >asm
> >  mov   al,[b]
> >  mov   cl,[times]
> >  ror   al,cl
> >end;

> No no. Those operations typically have to be fast. A procedure call
> creates much overhead. One can just use:

> var x:word;

> begin
>   x:=100;
>   asm ror x,5 end;
>   writeln(x);
> end.

I wasn't exactly going for speed, just trying to get the point across --
but you do raise a good point.  OTOH, depending on the application,
enough of those "asm ... end;" minor assembly codes can make a mess out
of code, especially where unknown rotations occur.  Also something that
might want to be considered is that your code above only works on 286,
where there's a chance of demand to use on an 8086.

But there's a common ground between speed and flexibility -- inline
code.  The procedure overhead can be nearly (though not 100%) eliminated
by using inline code (which also works in versions earlier than TP6.0,
where BASM isn't an option).  Try this:

function ror_bi (b, times : byte) : byte; inline (
  $59/         {pop   cx}
  $58/         {pop   ax}
  $d2/$c8      {ror   al,cl}
);

function rol_bi (b, times : byte) : byte; inline (
  $59/         {pop   cx}
  $58/         {pop   ax}
  $d2/$c0      {rol   al,cl}
);

You can still call these like a function, but there's a lot less
overhead since it inserts those 4 bytes (plus code to push b and times
onto the stack).  1 million iterations of the BASM version on my 486
took 3.90s.  The same with the inline took 0.99s.  Of course, a single
"asm ror [var],5; end;" is going to be the fastest of all (timed at
0.71s), but I don't think it would help speed in any but the tightest
loops, and doesn't lend to readability of code.

Quote
> [...]

> Osmo

--
Scott Earnest                      | _,-""-_,-""-_,-""-_,-""-_,-""-_,-"
|
set...@ix.netcom.com (primary)     | We now return you to our regularly
|
siny...@{*word*104}space.org (alternate) | scheduled chaos and mayhem. . . .
|

Re:Shifting and Rotating bits in Pascal


In article <329E876C.2...@ix.netcom.com>,
Scott Earnest  <set...@ix.netcom.com> wrote:

Quote
>Osmo Ronkanen wrote:
...

>> var x:word;

>> begin
>>   x:=100;
>>   asm ror x,5 end;
>>   writeln(x);
>> end.

>I wasn't exactly going for speed, just trying to get the point across --
>but you do raise a good point.  OTOH, depending on the application,
>enough of those "asm ... end;" minor assembly codes can make a mess out
>of code, especially where unknown rotations occur.  Also something that
>might want to be considered is that your code above only works on 286,
>where there's a chance of demand to use on an 8086.

8086 is history but should there be a need to compile the code for it,
it can be easily modified.

I do not think the code is unreadable. What would make it unreadable?
The "asm" word? IMO it is just as readable as x:=x shr 5.

- Show quoted text -

Quote

>But there's a common ground between speed and flexibility -- inline
>code.  The procedure overhead can be nearly (though not 100%) eliminated
>by using inline code (which also works in versions earlier than TP6.0,
>where BASM isn't an option).  Try this:

>function ror_bi (b, times : byte) : byte; inline (
>  $59/         {pop   cx}
>  $58/         {pop   ax}
>  $d2/$c8      {ror   al,cl}
>);

>function rol_bi (b, times : byte) : byte; inline (
>  $59/         {pop   cx}
>  $58/         {pop   ax}
>  $d2/$c0      {rol   al,cl}
>);

That _code_ is hardly readable.

Osmo

Re:Shifting and Rotating bits in Pascal


Quote
Osmo Ronkanen wrote:
> [...]

> >I wasn't exactly going for speed, just trying to get the point across --
> >but you do raise a good point.  OTOH, depending on the application,
> >enough of those "asm ... end;" minor assembly codes can make a mess out

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Quote
> >of code, especially where unknown rotations occur.  Also something that

   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Quote
> >might want to be considered is that your code above only works on 286,
> >where there's a chance of demand to use on an 8086.

> [...]

> I do not think the code is unreadable. What would make it unreadable?
> The "asm" word? IMO it is just as readable as x:=x shr 5.

Yes, *that* is readable, because it's a simple expression.  Look back at
my text I highlighted above.  Anything more complex, and you have a
whole cascade of statements.  Suppose, you have a code fragment that
does (in pseudocode):

 a := x*(m ROL p) + y*(n ROR q)*(o SHL r) + z;

Using the inline functions, you can write it in real code as:

  a := x*rol_bi(m,p) + y*ror_bi(n,q)*(o shl r) + z;

Now, your exercise is to concisely rewrite that using asm blocks as
needed.

Quote
> >But there's a common ground between speed and flexibility -- inline
> >code.  The procedure overhead can be nearly (though not 100%) eliminated
> >by using inline code (which also works in versions earlier than TP6.0,
> >where BASM isn't an option).  Try this:

> >function ror_bi (b, times : byte) : byte; inline (
> >  $59/         {pop   cx}
> >  $58/         {pop   ax}
> >  $d2/$c8      {ror   al,cl}
> >);

> >function rol_bi (b, times : byte) : byte; inline (
> >  $59/         {pop   cx}
> >  $58/         {pop   ax}
> >  $d2/$c0      {rol   al,cl}
> >);

> That _code_ is hardly readable.

For all practical purposes, "function ror_bi (b, times : byte) : byte;"
and "function rol_bi (b, times : byte) : byte;" are all you need to know
here.  The comments provide a practical explanation of what the code
does.  In the end, the code stays hidden and out of the way where you
actually need it, since all you use is a function call.  And since the
code stays out of the way, the end product will be more likely to
express what it actually means.

Quote
> Osmo

--
Scott Earnest                      | _,-""-_,-""-_,-""-_,-""-_,-""-_,-"
|
set...@ix.netcom.com (primary)     | We now return you to our regularly
|
siny...@{*word*104}space.org (alternate) | scheduled chaos and mayhem. . . .
|

Other Threads