What is the C# equivalent (.NET 2.0) of _rotl
and _rotr
from C++?
9 Answers
Is this what you are trying to do?
Jon Skeet answered this in another site
Basically what you want is
(for left)
(original << bits) | (original >> (32 - bits))
or
(for right)
(original >> bits) | (original << (32 - bits))
Also, as Mehrdad has already suggested, this only works for uint, which is the example that Jon gives as well.
-
This works correctly only if
original
isuint
. Note that Jon Skeet does it withuint
. Commented May 1, 2009 at 16:26 -
-
4Just delete the
32
to leave you with(original << bits) | (original >> ( -bits))
and you've code that works with the other unsigned types, too. Commented Dec 20, 2013 at 16:46 -
I have to rotate a byte, For example,
"10001100" (140)
to get"0001101 (13) "
. I tried mentioned solution but no success. Any help?– MUTCommented Nov 10, 2017 at 6:59 -
2In
System.Numerics
namespace, there isBitOperations.RotateLeft
andBitOperations.RotateRight
– MustafaCommented Jun 4, 2021 at 3:03
There's no built-in language feature for bit rotation in C#, but these extension methods should do the job:
public static uint RotateLeft(this uint value, int count)
{
return (value << count) | (value >> (32 - count))
}
public static uint RotateRight(this uint value, int count)
{
return (value >> count) | (value << (32 - count))
}
Note: As Mehrdad points out, right-shift (>>
) for signed integers is a peculiarity: it fills the MSBs with sign bit rather than 0 as it does for unsigned numbers. I've now changed the methods to take and return uint
(unsigned 32-bit integer) instead - this is also in greater accordance with the C++ rotl
and rotr
functions. If you want to rotate integers, just case them before passing, and again cast the return value, of course.
Example usage:
int foo1 = 8.RotateRight(3); // foo1 = 1
int foo2 = int.MinValue.RotateLeft(3); // foo2 = 4
(Note that int.MinValue
is 111111111111111111111111 - 32 1s in binary.)
-
1@Mehrdad: Yeah, just realised that as I posted. Fixed now. :)– NoldorinCommented May 1, 2009 at 16:13
-
1I think this will fail for negative numbers. You probably want to force the values to be unsigned.– plinthCommented May 1, 2009 at 16:15
-
1@plinth: It won't fail. The bitwise operations work exactly the same for signed and unsigned numbers, only that the number represented by signed ints can change sign during bit shifting/rotation because of the two's complement system.– NoldorinCommented May 1, 2009 at 16:17
-
@Mehrdad: So I learnt something new. :) Will edit the post to fix it.– NoldorinCommented May 1, 2009 at 16:23
-
1Note that RjuJIT will detect this pattern and emit rol and ror instructions, at least on an x86 platform in 2018 it does, but not sure when this started happening.– redcalxCommented Mar 23, 2018 at 16:27
With the latest C# 7, you can now create by-ref extension methods, so you can get rid of the busywork of constantly storing the return value from the helper function back into the variable.
This streamlines the rotate functions nicely, and eliminates a common class of bug where you forget to re-store the function's return value, yet while possibly introducing a new, completely different type of bug--where ValueTypes
are inadvertently getting modified in-situ when you didn't want or expect them to be.
public static void Rol(ref this ulong ul) => ul = (ul << 1) | (ul >> 63);
public static void Rol(ref this ulong ul, int N) => ul = (ul << N) | (ul >> (64 - N));
public static void Ror(ref this ulong ul) => ul = (ul << 63) | (ul >> 1);
public static void Ror(ref this ulong ul, int N) => ul = (ul << (64 - N)) | (ul >> N);
/// note: ---^ ^---^--- extension method can now use 'ref' for ByRef semantics
Usually I would be sure to put [MethodImpl(MethodImplOptions.AggressiveInlining)]
on small methods like these, but after some investigation (on x64) I found out that it's not necessary at all here. If the JIT determines the method is eligible (for example, if you uncheck the VisualStudio debugger checkbox 'Suppress JIT Optimization', which is enabled by default) the methods will inlined regardless, and that is the case here.
In case the term is unfamiliar, JIT, or "just-in-time" refers to the one-time conversion of IL instructions into native code tuned for the platform detected at runtime, a process which happens on-demand, per-method as a .NET program runs.
To demonstrate the use of a by-ref extension method, I'll focus just on the first method shown above "rotate left", and compare the JIT output between the traditional by-value extension method and the newer by-ref approach. Here are the two test methods to be compared on x64 Release in .NET 4.7 on Windows 10. As noted above, this will be with JIT optimization 'not-suppressed', so under these test conditions as you'll see, the functions will completely disappear into inline code.
static ulong Rol_ByVal(this ulong ul) => (ul << 1) | (ul >> 63);
static void Rol_ByRef(ref this ulong ul) => ul = (ul << 1) | (ul >> 63);
// notice reassignment here ---^ (c̲a̲l̲l̲e̲e̲ doing it instead of caller)
And here is the C# code for each corresponding call site. Since the fully JIT-optimized AMD64 code is so small, I can just include it here as well. This is the optimal case:
static ulong x = 1; // static so it won't be optimized away in this simple test
// ------- ByVal extension method; c̲a̲l̲l̲e̲r̲ must reassign 'x' with the result -------
x = x.Rol_ByVal();
// 00007FF969CC0481 mov rax,qword ptr [7FF969BA4888h]
// 00007FF969CC0487 rol rax,1
// 00007FF969CC048A mov qword ptr [7FF969BA4888h],rax
// ------- New in C#7, ByRef extension method can directly alter 'x' in-situ -------
x.Rol_ByRef();
// 00007FF969CC0491 rol qword ptr [7FF969BA4888h],1
Wow. Yes, that's no joke. Right off the bat we can see that the glaring lack of an OpCodes.Rot
-family of instructions in the ECMA CIL (.NET) intermediate language is pretty much of a non-issue; The jitter was able to see through our pile of C# workaround code (ul << 1) | (ul >> 63)
to divine its essential intent, which in both cases the x64 JIT implements by simply emitting a native rol
instruction. Impressively, the ByRef version uses a single instruction to perform the rotation directly on the main-memory target address without even loading it into a register.
In the ByVal case, you can still see a residual trace of the excess copying which was necessary to leave the caller's original value unchanged, prior to the called method being entirely optimized-away (as is the essence of value-type semantics). For integer rotate here, it's just an extra fetch/store of the target integer into a 64-bit register rax
.
To clarify that, let's re-suppress JIT optimizations in the debugging session. Doing so will make our helper extension methods come back, with full bodies and stack frames to better explain the first sentence of the preceding paragraph. First, let's look at the call sites. Here we can see the effect of traditional ValueType
semantics, which boils down to ensuring that no lower stack frame can manipulate any parent frame's ValueType
copies:
by-value:
x = x.Rol_ByVal();
// 00007FF969CE049C mov rcx,qword ptr [7FF969BC4888h]
// 00007FF969CE04A3 call 00007FF969CE00A8
// 00007FF969CE04A8 mov qword ptr [rbp-8],rax
// 00007FF969CE04AC mov rcx,qword ptr [rbp-8]
// 00007FF969CE04B0 mov qword ptr [7FF969BC4888h],rcx
by-reference
x.Rol_ByRef();
// 00007FF969CE04B7 mov rcx,7FF969BC4888h
// 00007FF969CE04C1 call 00007FF969CE00B0
// ...all done, nothing to do here; the callee did everything in-place for us
As we might expect from the C# code associated with each of these two fragments, we see that the by-val caller has a bunch of work to do after the call returns. This is the process of overwriting the parent copy of the ulong
value 'x' with the completely independent ulong
value that's returned in the rax
register.
Now let's look at the code for the called target functions. Seeing them requires forcing the JIT to "suppress" the optimizations. The following is the native code the x64 Release JIT emits for Rol_ByVal
and Rol_ByRef
functions.
In order to focus on the tiny but crucial difference between the two, I've stripped away some of administrative boilerplate. (I left the stack frame setup and teardown for context, and to show how in this example, that ancillary stuff pretty much dwarfs the actual contentful instructions.) Can you see the ByRef's indirection at work? Well, it helps that I pointed it out :-/
static ulong Rol_ByVal(this ulong ul) => (ul << 1) | (ul >> 63);
// 00007FF969CD0760 push rbp
// 00007FF969CD0761 sub rsp,20h
// 00007FF969CD0765 lea rbp,[rsp+20h]
// ...
// 00007FF969CE0E4C mov rax,qword ptr [rbp+10h]
// 00007FF969CE0E50 rol rax,1
// 00007FF969CD0798 lea rsp,[rbp]
// 00007FF969CD079C pop rbp
// 00007FF969CD079D ret
static void Rol_ByRef(ref this ulong ul) => ul = (ul << 1) | (ul >> 63);
// 00007FF969CD0760 push rbp
// 00007FF969CD0761 sub rsp,20h
// 00007FF969CD0765 lea rbp,[rsp+20h]
// ...
// 00007FF969CE0E8C mov rax,qword ptr [rbp+10h]
// 00007FF969CE0E90 rol qword ptr [rax],1 <--- !
// 00007FF969CD0798 lea rsp,[rbp]
// 00007FF969CD079C pop rbp
// 00007FF969CD079D ret
You might notice that both calls are in fact passing the parent's instance of the ulong
value by reference--both examples are identical in this regard. The parent indicates the address where its private copy of ul
resides in the upper stack frame. Turns out it's not necessary to insulate callees from reading those instances where they lie, as long as we can be sure they never write to those pointers. This is a "lazy" or deferred approach which assigns to each lower (child) stack frame the responsibility for preserving the ValueType semantics of its higher-up callers. There's no need for a caller to proactively copy any ValueType
passed down to a child frame if the child never ends up overwriting it; to maximize the avoidance of unnecessary copying as much as possible, only the child can make the latest-possible determination.
Also interesting is that we might have an explanation here for the clunky use of rax
in the first 'ByVal' example I showed. After the by-value method had been completely reduced via inlining, why did the rotation still need to happen in a register?
Well in these latest two full-method-body versions its clear that the first method returns ulong
and the second is void
. Since a return value is passed in rax
, the ByVal method here has to fetch it into that register anyway, so it's a no-brainer to rotate it there too. Because the ByRef method doesn't need to return any value, it doesn't need to stick anything for its caller anywhere, let alone in rax
. It seems likely that "not having to bother with rax
" liberates the ByRef code to target the ulong
instance its parent has shared 'where it lies', using the fancy qword ptr
to indirect into the parent's stack frame memory, instead of using a register. So that's my speculative, but perhaps credible, explanation for the "residual rax
" mystery we saw earlier.
-
1
The naive version of shifting won't work. The reason is, right shifting signed numbers will fill the left bits with sign bit, not 0:
You can verify this fact with:
Console.WriteLine(-1 >> 1);
The correct way is:
public static int RotateLeft(this int value, int count)
{
uint val = (uint)value;
return (int)((val << count) | (val >> (32 - count)));
}
public static int RotateRight(this int value, int count)
{
uint val = (uint)value;
return (int)((val >> count) | (val << (32 - count)));
}
-
or you could change the extension method to bring in a uint and return a uint, which is what Jon did– JosephCommented May 1, 2009 at 16:24
-
@Joseph: In that case, you should do the cast manually when you call with an int. Commented May 1, 2009 at 16:27
-
Yeah, it would make more sense for the function just to take/return uint (that's what I've done in my updated post too). Otherwise, if you actually want to rotate a uint, you'd be casting 4 times when you don't in fact need to do any!– NoldorinCommented May 1, 2009 at 16:28
-
1Anyway guys, these stuff doesn't really add much value. I just submitted the answer to clarify the signed right shift fact which is really important to know when doing bitwise operations. Commented May 1, 2009 at 16:33
-
1+1 btw, since you did point out the issue with right-shifting signed ints.– NoldorinCommented May 1, 2009 at 16:43
For those using .NET Core 3.0 or .NET 5.0 and later, it's possible to use BitOperations.RotateLeft
and RotateRight
.
-
Just to add for anyone searching that this is found in the System.Numerics namespace. Commented Mar 8, 2021 at 9:53
-
1Note that these methods use hardware intrinsics when available on the underlying platform; otherwise, they use optimized software fallbacks. Using them is recommended over the purely software implementations. Commented Oct 11, 2022 at 5:44
Note that if you want to create overloads that operate on shorter integral values, you need to add an extra step, as shown in:
public static byte RotateLeft(
this byte value,
int count )
{
// Unlike the RotateLeft( uint, int ) and RotateLeft( ulong, int )
// overloads, we need to mask out the required bits of count
// manually, as the shift operaters will promote a byte to uint,
// and will not mask out the correct number of count bits.
count &= 0x07;
return (byte)((value << count) | (value >> (8 - count)));
}
The masking operation is not needed for the 32-bit and 64-bit overloads, as the shift operators themselves take care of it for those sizes of left-hand operands.
Recent dotnet versions have generic numerics the integer types have rotate functions like this:
public static UInt16 RotateLeft(UInt16 value, int rotateAmount);
If you don't have .NET Core 3.0+ for BitOperations.RotateLeft/RotateRight
then you might be able to use BitRotator.RotateLeft()
and BitRotator.RotateRight()
in Microsoft.VisualStudio.Utilities
BitRotator.RotateLeft(35, 2)
BitRotator.RotateRight(3, 5)
// if you are using string
string str=Convert.ToString(number,2);
str=str.PadLeft(32,'0');
//Rotate right
str = str.PadLeft(33, str[str.Length - 1]);
str= str.Remove(str.Length - 1);
number=Convert.ToInt32(str,2);
//Rotate left
str = str.PadRight(33, str[0]);
str= str.Remove(0,1);
number=Convert.ToInt32(str,2);
-
2