C# bitwise rotate left and rotate right

Question

What is the C# equivalent (.NET 2.0) of _rotl and _rotr from C++?

Solution 1

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.

Solution 2

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.)

Solution 3

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.

Solution 4

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

Solution 5

For those using .NET Core 3.0 or .NET 5.0 and later, it's possible to use BitOperations.RotateLeft and RotateRight.

View more solutions

Comments

[Noldorin]

@Mehrdad: Yeah, just realised that as I posted. Fixed now. :)

[plinth]

I think this will fail for negative numbers. You probably want to force the values to be unsigned.

[Noldorin]

@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.

[Noldorin]

@Mehrdad: So I learnt something new. :) Will edit the post to fix it.

[Joseph]

or you could change the extension method to bring in a uint and return a uint, which is what Jon did

[mmx]

This works correctly only if original is uint. Note that Jon Skeet does it with uint.

[mmx]

@Joseph: In that case, you should do the cast manually when you call with an int.

[Noldorin]

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!

[Joseph]

@Mehrdad That's correct, but I wasn't assuming it was an int to begin with.

[mmx]

Noldorin: You could create a set of extension methods for uint to. Anyway, it doesn't really matter much. These casts won't matter at the level of native code. It's not like that JIT generates instructions to do the cast. CPU doesn't really care :)

[mmx]

Anyway 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.

[Noldorin]

@Richard: That looks like bit magic and would probably take me a while to figure out. I'll take the poster's word that it works however. You're probably still better off just casting, as it's simple and doesn't require seperate functions for int and unit. However, that function may beat this one + casting in speed, though it's not something to bother about in general.

[Noldorin]

@Mehrdad: That is true, I'm sure, though I would still argue for have base methods that take uint for the sake of simplicitly/elegance. Indeed, you could then overload the methods for int if you wanted to avoid constantly casting inline. These are however petty points, as you say.

[Noldorin]

+1 btw, since you did point out the issue with right-shifting signed ints.

[Prithis]

@Mehrdad Luckly I was looking for a solution with 'uint'

[mmx]

@Richard: It'll work. It's not magic. First line of it is unnecessary. The second line is essentially what mentioned in this post. The first line means to zero out the MSBs of the number by "and"ing the input with some number like 00000011111 (L right bits are 1, rest is zero). To get such a number you'd want to decrement one from 1000000) :) There's no reason to zero out at all since the shift will do it automatically.

[Kendall Frey]

Good, I just had to mention that int.MinValue is actually 10000000000000000000000000000000.

[Noldorin]

@KendallFrey: I'm too lazy to count... is that 31 0s there? :-P If so, I think you are indeed right.

[Jon Hanna]

Just delete the 32 to leave you with (original << bits) | (original >> ( -bits)) and you've code that works with the other unsigned types, too.

[Michel de Ruiter]

That's very inefficient!

[MUT]

I have to rotate a byte, For example, "10001100" (140) to get "0001101 (13) ". I tried mentioned solution but no success. Any help?

[MUT]

I have to rotate a byte, For example, "10001100" (140) to get "0001101 (13) ". I tried mentioned solution but no success. Any help?

[MUT]

I have to rotate a byte, For example, "10001100" (140) to get "0001101 (13) ". I tried mentioned solution but no success. Any help?

[redcalx]

Note 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.

[moien]

nice demonstration. didn't know ref this before.

[Matt Jenkins]

Just to add for anyone searching that this is found in the System.Numerics namespace.

[Mustafa]

In System.Numerics namespace, there is BitOperations.RotateLeft and BitOperations.RotateRight