C#按位向左旋转和向右旋转
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/812022/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C# bitwise rotate left and rotate right
提问by Prithis
What is the C# equivalent (.NET 2.0) of _rotland _rotrfrom C++?
什么是的C＃当量（.NET 2.0）_rotl和_rotr从C ++？
采纳答案by Joseph
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.
此外，正如 Mehrdad 已经建议的那样，这仅适用于 uint，这也是 Jon 给出的示例。
回答by Noldorin
There's no built-in language feature for bit rotation in C#, but these extension methods should do the job:
C# 中没有用于位旋转的内置语言功能，但这些扩展方法应该可以完成这项工作：
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++ rotland rotrfunctions. If you want to rotate integers, just case them before passing, and again cast the return value, of course.
注意：正如 Mehrdad 指出的那样，>>有符号整数的右移 ( ) 是一个特性：它用符号位填充 MSB，而不是像无符号数字那样填充 0。我现在更改了获取和返回的方法uint（无符号 32 位整数） - 这也更符合 C++rotl和rotr函数。如果您想旋转整数，只需在传递之前将它们大小写，然后再次转换返回值，当然。
Example usage:
用法示例：
int foo1 = 8.RotateRight(3); // foo1 = 1
int foo2 = int.MinValue.RotateLeft(3); // foo2 = 4
(Note that int.MinValueis 111111111111111111111111 - 32 1s in binary.)
（请注意，这int.MinValue是 111111111111111111111111 - 二进制的 32 个 1。）
回答by Mehrdad Afshari
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:
幼稚的转移版本是行不通的。原因是，右移有符号数将用符号位填充左位，而不是 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)));
}
回答by John Beyer
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.
32 位和 64 位重载不需要屏蔽操作，因为移位运算符本身会为左手操作数的大小处理它。
回答by Altaf Hussain
// 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);
回答by Glenn Slayden
With the latest C# 7, you can now create by-refextension methods, so you can get rid of the busywork of constantly storing the return value from the helper function back into the variable.
使用最新的C# 7，您现在可以创建by-ref扩展方法，这样您就可以摆脱不断将辅助函数的返回值存储回变量的繁忙工作。
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 ValueTypesare inadvertently getting modified in-situwhen you didn't want or expect them to be.
这很好地简化了旋转函数，并消除了一类常见的错误，即您忘记重新存储函数的返回值，但同时可能会引入一种新的、完全不同类型的错误——当您ValueTypes无意中就地修改时不希望或期望他们成为。
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.
通常我肯定会[MethodImpl(MethodImplOptions.AggressiveInlining)]采用这样的小方法，但经过一些调查（在 x64 上）我发现这里根本没有必要。如果 JIT 确定该方法符合条件（例如，如果您取消选中 VisualStudio 调试器复选框'Suppress JIT Optimization'，默认情况下启用），则无论如何都会内联方法，这里就是这种情况。
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 .NETprogram runs.
如果术语不熟悉，JIT或“即时”是指将 IL 指令一次性转换为针对运行时检测到的平台调整的本机代码，这是一个按需发生的过程，每个方法如下一个.NET程序运行。
To demonstrate the use of a by-refextension method, I'll focus just on the first method shown above "rotate left", and compare the JIT output between the traditional by-valueextension method and the newer by-refapproach. Here are the two test methods to be compared on x64Releasein .NET 4.7on 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.
为了演示by-ref扩展方法的使用，我将只关注上面显示的第一种方法“向左旋转”，并比较传统的by-value扩展方法和较新的by-ref方法之间的 JIT 输出。这里有两种测试方法要在比较的x64版本的.NET 4.7在Windows 10，如上所述，这将是与JIT优化“不抑制”，所以在这些测试条件如你所见，该功能将完全消失在内联代码中。
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:
这是每个相应调用站点的 C# 代码。由于完全 JIT 优化的 AMD64 代码非常小，我也可以将它包含在这里。这是最佳情况：
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 rolinstruction. 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.
哇。是的，这不是开玩笑。马上我们就可以看到，ECMA CIL(.NET) 中间语言中明显缺乏一系列OpCodes.Rot指令几乎不是问题；抖动能够看穿我们的一堆 C# 解决方法代码来判断其基本意图，在这两种情况下，x64 JIT 都通过简单地发出本机指令来实现。令人印象深刻的是，ByRef 版本使用单个指令直接在主内存目标地址上执行轮换，甚至无需将其加载到寄存器中。(ul << 1) | (ul >> 63)rol
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.
在 ByVal 的情况下，在被调用的方法被完全优化掉（这是值类型语义的本质）之前，您仍然可以看到多余复制的残留痕迹，这是保持调用者原始值不变所必需的。对于这里的整数轮换，它只是将目标整数额外提取/存储到 64 位寄存器中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 ValueTypesemantics, which boils down to ensuring that no lower stack frame can manipulate any parent frame's ValueTypecopies:
为了澄清这一点，让我们在调试会话中重新抑制 JIT 优化。这样做会让我们的辅助扩展方法回来，用完整的主体和堆栈框架来更好地解释上一段的第一句话。首先，让我们看看呼叫站点。在这里我们可以看到传统ValueType语义的效果，归结为确保没有较低的堆栈框架可以操作任何父框架的ValueType副本：
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-valcaller has a bunch of work to do after the call returns. This is the process of overwriting the parent copy of the ulongvalue 'x' with the completely independent ulongvalue that's returned in the raxregister.
正如我们对与这两个片段中的每一个相关联的C#代码所期望的那样，我们看到by-val调用者在调用返回后有很多工作要做。这是ulong用寄存器中ulong返回的完全独立的值覆盖值“x”的父副本的过程rax。
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_ByValand Rol_ByReffunctions.
现在让我们看看被调用的目标函数的代码。看到它们需要强制 JIT“抑制”优化。以下是 x64 Release JIT 发出的本机代码Rol_ByVal和Rol_ByRef函数。
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 :-/
为了专注于两者之间微小但至关重要的区别，我去掉了一些管理样板。（我将堆栈框架的设置和拆卸留给上下文，并说明在这个例子中，辅助内容如何使实际的内容指令相形见绌。）你能看到 ByRef 的间接工作吗？好吧，我指出它有帮助：-/
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 ulongvalue by reference--both examples are identical in this regard. The parent indicates the address where its private copy of ulresides in the upper stack frame. Turns out it's not necessary to insulate callees from readingthose 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 ValueTypesemanticsof its higher-up callers. There's no need for a caller to proactively copy any ValueTypepassed 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.
您可能会注意到，这两个调用实际上都是ulong通过引用传递值的父级实例——这两个示例在这方面是相同的。parent 指示其私有副本ul驻留在上层堆栈帧中的地址。事实证明，没有必要让被调用者读取它们所在的实例，只要我们可以确定它们永远不会写入这些指针。这是一种“懒惰”或延迟的方法，它为每个较低（子）堆栈框架分配了保留其较高调用者的ValueType语义的责任。呼叫者无需主动复制任何ValueType如果子框架永远不会覆盖它，则传递给子框架；为了最大限度地避免不必要的抄袭，只有孩子才能做出可能的最新决定。
Also interesting is that we might have an explanation here for the clunky use of raxin 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?
同样有趣的是，我们可能在这里对rax我展示的第一个“ByVal”示例中笨拙地使用 进行了解释。通过内联完全减少了按值方法后，为什么还需要在寄存器中进行轮换？
Well in these latest two full-method-body versions its clear that the first method returns ulongand 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 ulonginstance its parent has shared 'where it lies', using the fancy qword ptrto 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.
那么在这两个最新的完整方法体版本中，很明显第一个方法返回ulong，第二个方法是void. 因为传入了一个返回值rax，所以这里的 ByVal 方法无论如何都必须将它提取到那个寄存器中，所以在那里旋转它也很容易。因为 ByRef 方法不需要返回任何值，所以它不需要在任何地方为其调用者粘贴任何东西，更不用说在rax. 似乎“不必费心rax”解放了 ByRef 代码以定位ulong其父级共享的“它所在的位置”的实例，使用qword ptr间接到父级堆栈帧内存的方式，而不是使用寄存器。所以这就是我对“残差rax”的推测，但也许是可信的解释
