views:

2934

answers:

6

I know that the following is true

int i = 17; //binary 10001
int j = i << 1; //decimal 34, binary 100010

But, if you shift too far, the bits fall off the end. Where this happens is a matter of the size of integer you are working with.

Is there a way to perform a shift so that the bits rotate around to the other side? I'm looking for a single operation, not a for loop.

+17  A: 

If you know the size of type, you could do something like:

uint i = 17;
uint j = i << 1 | i >> 15;

... which would perform a circular shift of a 16 bit value.

As a generalization to circular shift left n bits, on a b bit variable:

var input = 17;
var result = i << n | i >> (b - n);


@The comment, it appears that C# does treat the high bit of signed values differently. I found some info on this here. I also changed the example to use a uint.

Chris Marasti-Georg
Since I don't know C#, are the shift operators doing arithmetic or logic shifts? If arithmetic, then this algorithm can't be used for 64-bit signed integers.
ΤΖΩΤΖΙΟΥ
So perhaps both the 'int' and 'var' types should be prefixed with an 'unsigned' modifier, of course if C# allows that.
ΤΖΩΤΖΙΟΥ
Thanks for catching that.
Chris Marasti-Georg
Well, rotation of bits only makes sense with unsigned integers anyway.
Lasse V. Karlsen
+5  A: 

Chris's answer is good, and I won't add to it.

To answer Keith's question, word rotations have a lot of uses, especially in cryptography. Have a look at various message digest algorithms, such as MD5, or the SHA family, for starters.

Chris Jester-Young
A: 

@Keith Sirmons,

I believe (don't quote me on it) that this might have some application in cryptography. Basically any situation where you want a reversible operation performed on data. Doing a regular bit shift causes a loss of data when bits fall off the end.

Personally, I was experimenting with encoding a list of 8-8bit integers in a single Int64 variable and rotating the list. Rather than the traditional 9 operations (store the first element, move 7 items, restore temp to the end of the list), it is now one operation. Not entirely useful for day-to-day stuff, but I wanted to see if it could be done quicker.

Jason Z
Jason, interesting application of the concept. Did you consider also maintaining a "pointer" into the list, representing the first integer, and just moving that around to achieve the same sort of affect?
Chris Marasti-Georg
Chris, I guess that would be a simple implementation of a circular list, wouldn't it? Hadn't considered it. I believe I was interested in an optimal solution, both in terms of time and space. A pointer would be 32 bits (or 64), taking half the size of the list to store the pointer.
Jason Z
+2  A: 

One year ago I've to implement MD4 for my undergraduate thesis. Here it is my implementation of circular bit shift using a UInt32.

private UInt32 RotateLeft(UInt32 x, Byte n)
{
      return (UInt32)(((x) << (n)) | ((x) >> (32 - (n))));
}
jaircazarin-old-account
A: 

Just as reference on how to do it, this two functions work perfectly for rotating the bits of 1/2word:

static public uint ShiftRight(uint z_value, int z_shift)
{
    return ((z_value >> z_shift) | (z_value << (16 - z_shift))) & 0x0000FFFF;
}

static public uint ShiftLeft(uint z_value, int z_shift)
{
    return ((z_value << z_shift) | (z_value >> (16 - z_shift))) & 0x0000FFFF;
}

It would be easy to extend it for any given size.

yeyeyerman