C# bitwise rotate left and rotate right
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.
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.)
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.