bit rotation

[=?Utf-8?B?QnJpYW4=?=]

Looking around in the class libraries there doesn't appear to be any methods
that do the equivalent of the C runtime lib functions rotr() and rotl(). I
wrote the following but then began to wonder if someone had some generic
methods that would handle differnet word sizes and and signed datatypes.

Doing bit shifting on the signed datatypes kind of surprised me originally.
I thought that if you shifted -2147483643 (0x80000005) by 8 bits right by
doing the folliowing:
-2147483643 >16
you would get 0x00058000 but you don't. Instead you get 0xffff8000 becuase
the shift keeps sign extending the thing. So I wrote my own signed int shift
like so:

public static int rotr(int val, int shift)
{
return (val & 0x7fffffff) >shift | val << (32 - shift) | ((val
< 0) ? 0x01 << (32 - shift - 1) : 0);
}
public static int rotl(int val, int shift)
{
return (val & 0x7fffffff) >(32 - shift) | val << shift | ((val
< 0) ? 0x01 << (shift - 1) : 0);
}


Where I strip off the high bit and handle it spearately.

Does anyone have any generic methods that do this for all integer sizes both
signed and unsigned? If so I would like to see them as I've spent a little
while trying and can't seem to get it. Or...if someone has a better way I'd
like to know that also...or if I just missed the implementation of these
things in the class lib.

thanks.

[Jeroen Mostert]

Re: bit rotation

Brian wrote:

Looking around in the class libraries there doesn't appear to be any methods
that do the equivalent of the C runtime lib functions rotr() and rotl().

Those are not standard functions, so it depends on what C runtime you're
talking about. :-)

I wrote the following but then began to wonder if someone had some
generic methods that would handle differnet word sizes and and signed
datatypes.
>

There's no real reason to worry too much: there are only three word sizes in
..NET, and rotating on signed types with preservation of the sign is unlikely
to be of any use.

Doing bit shifting on the signed datatypes kind of surprised me originally.
I thought that if you shifted -2147483643 (0x80000005) by 8 bits right by
doing the folliowing:
-2147483643 >16

That would be shifting by 16 bits.

you would get 0x00058000 but you don't.

Well, for that you'd actually need to *rotate* the value rather than shift it.

I have full confidence that you were exact to the computer, but still. :-)

Instead you get 0xffff8000 becuase the shift keeps sign extending the
thing. So I wrote my own signed int shift like so:
>
public static int rotr(int val, int shift)
{
return (val & 0x7fffffff) >shift | val << (32 - shift) | ((val
< 0) ? 0x01 << (32 - shift - 1) : 0);
}
public static int rotl(int val, int shift)
{
return (val & 0x7fffffff) >(32 - shift) | val << shift | ((val
< 0) ? 0x01 << (shift - 1) : 0);
}
>
Where I strip off the high bit and handle it spearately.

If your intention is to treat signed types as if they were unsigned, it's a
lot easier to just do that:

[CLSCompliant(fa lse)]
public static uint RotateRight(uin t value, int count) {
if (count < 0) throw new ArgumentOutOfRa ngeException("c ount");
count %= 32;
return (value >count) | (value << (32 - count));
}

public static int RotateRight(int value, int count) {
return unchecked((int) RotateRight((ui nt) value, count));
}

A few notes:
- The CLSCompliant attribute marks this method as not conforming to the
Common Language Specification, since you can't use it if your language has
no unsigned types. That's no problem since we provide an alternative with
only signed types. This attribute is only necessary if you're exporting this
function in a library.
- I choose to consider a negative count an error, but not count 32, since
it has a reasonable interpretation.
- The "unchecked" suppresses any integer overflow detection (if compiled
with this) for converting the values between signed and unsigned. We don't
need "unchecked" in the unsigned version because bit shifting never produces
overflows.

Does anyone have any generic methods that do this for all integer sizes both
signed and unsigned?

Well, there are only three differently-sized integral types in .NET (byte,
int, long) and unlike C their sizes are exact, so these overloads would be
fairly straightforward . You cannot write a single method that takes any
integer (unless you use Object, which would be bad), and while you could
write just the ulong method and have the rest delegate to it the added
complexity isn't worth it.

Also, operations on bytes are not that common since they're promoted to ints
by just about every operation, so you might not need rotation on bytes at all.

--
J.

http://symbolsprose.blogspot.com

[Ben Voigt [C++ MVP]]

Re: bit rotation

Well, there are only three differently-sized integral types in .NET

(byte, int, long) and unlike C their sizes are exact, so these

Those are 8, 32, and 64 bits, respectively. You forgot short, which is 16
bits.

For such work it may be preferable to use the names System.Byte,
System.UInt16, System.UInt32, System.UInt64 which specifically call out the
number of bits (except for 8).