C# bitwise rotate left and rotate right

Question

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

Answer 1

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

Answer 2

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)((value >> count) | (value << (32 - count)));
}

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

Answer 4

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

Answer 5

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.

Answer 6

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.