Is there a way to perform a circular bit shift in C#?

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.

Where would an operation of this type be used? What is the purpose behind doing a Bit Rotate? I don't need to know, but am just interested in ever expanding knowledge. Keith — Keith Sirmons, Oct 07 '08 at 14:32
a very good question. I just checked the generated code and the C# compiler doesn't generate code that uses the rotate instructions of the CPU (not that the x86 architecture has them since the 8086...). This is a shame. C does this optimization. Also rotations are very important for crypto and dsp tasks. — Nils Pipenbrinck, Jun 08 '09 at 01:45

Chris Marasti-Georg · Accepted Answer · 2014-02-05T16:43:53.623

55

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.

edited Feb 05 '14 at 16:43

answered Aug 29 '08 at 19:57

Chris Marasti-Georg

34,091
15
92
137

1

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. – tzot Oct 06 '08 at 15:20
So perhaps both the 'int' and 'var' types should be prefixed with an 'unsigned' modifier, of course if C# allows that. – tzot Oct 06 '08 at 15:21
5

Well, rotation of bits only makes sense with unsigned integers anyway. – Lasse V. Karlsen Aug 05 '09 at 12:37
2

@LasseV.Karlsen: I wouldn't necessarily agree with that. [`GetHashCode`](http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx) returns a (signed) `int`, and if you want to evenly distribute hash codes by using the full 32 bits of that (which *can* involve bit rotation), the sign doesn't really matter - and apparently gets in the way of bit rotation. – O. R. Mapper Oct 16 '13 at 12:17
1

If you use `i << n | i >> -n` (or alternatively, `i << n | i >> ~n >> 1`) then you don't have to change the value of `b` for different sizes. It could theoretically be marginally faster too, but not so that you'd ever notice. – Jon Hanna Dec 20 '13 at 16:24
@O.R.Mapper true, but really `GetHashCode` should be considered a `uint` but it has to be an `int` to be CLS compliant. If you're going to bit-fiddle with it, it really only makes sense to either cast to `uint` or mask out the sign bit. Most uses of the result will need you to mask out the sign bit anyway (e.g. indexing from a modulus). – Jon Hanna Dec 20 '13 at 16:27
Also of note, the second example will never work on its own -- you use the undeclared variable "i" instead of the intended "input". (And if you switch it to input, the compiler will still turn that into a regular int, not a uint). – BrainSlugs83 Feb 01 '14 at 00:38
2

Strange that it would even need this much code, given the fact both `ror` and `rol` are part of the bare x86 CPU instruction set. Couldn't they just have made a `<<>` instruction or something for that in C#? – Nyerguds Nov 21 '16 at 08:18

score 12 · Answer 2 · edited Mar 14 '17 at 19:18

12

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)));
}

edited Mar 14 '17 at 19:18

Tim Lovell-Smith

15,310
14
76
93

answered Oct 09 '08 at 02:42

jaircazarin-old-account

2,875
3
20
17

score 7 · Answer 3 · answered Feb 11 '20 at 02:09

Sincce .NET Core 3.0 and up there's BitOperations.RotateLeft() and BitOperations.RotateRight() so you can just use something like

BitOperations.RotateRight(12, 3);
BitOperations.RotateLeft(34L, 5);

In previous versions you can use BitRotator.RotateLeft() and BitRotator.RotateRight() in Microsoft.VisualStudio.Utilities

score 4 · Answer 4 · edited Jan 07 '20 at 06:42

Just as reference on how to do it, these 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.

score 1 · Answer 5 · answered Mar 12 '21 at 01:23

The extension methods for rotating bits of a uint (32 bits):

public static uint ROR(this uint x, int nbitsShift)
    => (x >> nbitsShift) | (x << (32 - nbitsShift));

public static uint ROL(this uint x, int nbitsShift)
    => (x << nbitsShift) | (x >> (32 - nbitsShift));

Is there a way to perform a circular bit shift in C#?

5 Answers5

Linked

Related