Is there a way to perform a circular bit shift in C#?
-
09-06-2019 - |
Question
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.
Solution
If you know the size of type, you could do something like:
uint i = 17;
uint j = i << 1 | i >> 31;
... which would perform a circular shift of a 32 bit value.
As a generalization to circular shift left n bits, on a b bit variable:
/*some unsigned numeric type*/ input = 17;
var result = input << n | input >> (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.
OTHER TIPS
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)));
}
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.
I have to admit, I just did a search for "C# bit rotate" and found a link to a page with a Java class that would be easily adapted to C#
I also found this in Google Book which is a C++ function with similar behavior
The most famous application is the solution to the Josephus problem (as discussed in Concrete Mathematics, see http://oeis.org/A006257). This is basically a puzzle with no obvious applications. In this video, I demonstrated connections between the second order Josephus problem and complete balanced trees. It's still not an application, but moving slightly in the right direction.