Bitwise Circular Shift in C#

[Ian Uy]

Good Day, Is there a fast way to do Circular Shift (Rotate) in C#? Given a byte, I would like to be able to Rotate it N times. Thanks! :)

It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.

[Lost User]

I love this sort of stuff. Something I just hacked together:

	static byte CircularBitwiseShiftLeft(byte value, int times)
	{
		for (int i = 0; i < times % 8; i++)
		{
			value = (byte)((value << 1) | (value >> 7));
		}

		return value;
	}

	static byte CircularBitwiseShiftRight(byte value, int times)
	{
		for (int i = 0; i < times % 8; i++)
		{
			value = (byte)((value >> 1) | ((value & 0x1) << 7));
		}

		return value;
	}

/edit: added % 8 to eliminate duplicate rotations for times > 8 regards

modified on Thursday, July 24, 2008 1:32 PM

[Ian Uy]

Thanks, For efficiency, can I put: times%=16; Since after 16 rotations, its just 0. I mean, rot 17 is just rot 1.

It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.

[Lost User]

Good point, I'd rather do:

for (int i = 0; i < times % 8; i++)

regards

[Luc Pattyn]

Hi, if it is a byte, then it is modulo 8 you want. IMO, assuming you need a lot of those, the fastest implementation for byte data is using a two-dimensional array, properly initialized. byteShifter[shiftAmount%8][value]; Of course you could store all kinds of 2-operand functions in such a table, not just rotates. For larger data items, this approach is becoming memory costly. FYI: with C# modulo may yield negative values for negative inputs, you may have to correct for that. :)

Luc Pattyn [Forum Guidelines] [My Articles]

---

Voting for dummies? No thanks. X|

---

[PIEBALDconsult]

Ew, not loops.

public static byte
RightRotate
(
byte value
,
byte times
)
{
times %= 8 ;
return ( (byte) ( value >> times | value << 8-times ) ) ;
}

public static byte
LeftRotate
(
byte value
,
byte times
)
{
times %= 8 ;
return ( (byte) ( value << times | value >> 8-times ) ) ;
}

But as Luc says... table lookup.

[Ennis Ray Lynch Jr]

I don't think << is circular but I do believe there is an opcode which is which would mean C++ and not C#

Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway

[Guffa]

PIEBALDconsult wrote:

But as Luc says... table lookup.

Would that really be faster? It looks to me like validating the indexes and calculating the offset in the array data would be about as much work as just calculating the value.

Despite everything, the person most likely to be fooling you next is yourself.

[PIEBALDconsult]

Then use unsafe code?

[Ian Uy]

True, << and >> means Left Shift and Right Shift. But when done in a specific way, it can be "tricked" to do Circular shifts. :)

It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.