C#按位向左旋转并向右旋转

Question

什么是的C#当量(.NET 2.0)_rotl和_rotr从C++？

Answer 1

这是你想要做的吗？

Jon Skeet在另一个网站上回答了这个问题

基本上你想要的是

(左)

(original << bits) | (original >> (32 - bits))

要么

(右)

(original >> bits) | (original << (32 - bits))

另外,正如Mehrdad已经建议的那样,这只适用于uint,这也是Jon给出的例子.

Answer 2

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

注意:正如Mehrdad所指出的那样,>>对于有符号整数的右移()是一种特殊性:它用符号位而不是0来填充MSB,就像对无符号数一样.我现在改变了采用和返回的方法uint(无符号32位整数) - 这也更符合C++ rotl和rotr函数.如果你想旋转整数,只需在传递之前将它们设置为case,然后再次转换返回值.

用法示例:

int foo1 = 8.RotateRight(3); // foo1 = 1
int foo2 = int.MinValue.RotateLeft(3); // foo2 = 4

(注意,这int.MinValue是111111111111111111111111 - 二进制的32个1.)

Answer 3

使用最新的C#7,您现在可以创建by-ref扩展方法,这样您就可以摆脱不断将辅助函数的返回值存储回变量的繁忙工作.

这很好地简化了旋转函数,并消除了一个常见的bug类,你忘记重新存储函数的返回值,但可能会引入一个新的,完全不同类型的bug - 当你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

通常我会确保[MethodImpl(MethodImplOptions.AggressiveInlining)]采用这样的小方法,但经过一些调查(在x64上)后我发现它根本就没有必要.如果JIT确定该方法是合格的(例如,如果取消选中VisualStudio调试器复选框'Suppress JIT Optimization',默认情况下已启用),则无论如何都会内联方法,这就是这种情况.

_{如果术语不熟悉,JIT或"及时"是指将IL指令一次性转换为针对在运行时检测到的平台调整的本机代码,该过程按需发生,每个方法为一个.NET程序运行.}

为了演示使用by-ref扩展方法,我将只关注上面显示的第一个方法"向左旋转",并比较传统的按值扩展方法和更新的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)

这是每个相应呼叫站点的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  

哇.是的,那不是开玩笑.马上,我们可以看到ECMA CIL(.NET)中间语言中明显缺乏一系列OpCodes.Rot指令几乎不是问题.抖动能够透过我们的一堆C#变通方法代码来理解它的基本意图,在两种情况下x64 JIT都是通过简单地发出本机指令来实现的.令人印象深刻的是,ByRef版本使用单个指令直接在主存储器目标地址上执行旋转,甚至无需将其加载到寄存器中.(ul << 1) | (ul >> 63)rol

在ByVal的情况下,您仍然可以看到多余复制的残余痕迹,这是在调用方法完全优化之前保持调用者原始值不变所必需的(这是值类型语义的本质).对于这里的整数旋转,它只是将目标整数额外提取/存储到64位寄存器中rax.

为了澄清这一点,让我们在调试会话中重新抑制JIT优化.这样做会使我们的辅助扩展方法返回,使用完整的主体和堆栈框架来更好地解释前一段的第一句话.首先,我们来看看呼叫网站.在这里我们可以看到传统ValueType语义的效果,归结为确保没有较低的堆栈框架可以操作任何父框架的ValueType副本:

通过值:

                     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  

引用

                     x.Rol_ByRef();
// 00007FF969CE04B7  mov         rcx,7FF969BC4888h  
// 00007FF969CE04C1  call        00007FF969CE00B0
//             ...all done, nothing to do here; the callee did everything in-place for us

正如我们可能期望从与这两个片段中的每一个相关联的C#代码,我们看到在调用返回后,by-val调用者有许多工作要做.这是使用在寄存器中返回ulong的完全独立的ulong值覆盖值'x' 的父副本的过程rax.

现在让我们看一下被调用目标函数的代码.看到它们需要强制JIT"抑制"优化.以下是x64 Release JIT发出的本机代码Rol_ByVal和Rol_ByRef函数.

为了专注于两者之间微小而重要的区别,我剥夺了一些行政样板.(我离开堆栈框架设置并拆除上下文,并显示在这个例子中,辅助的东西几乎使实际的内容指令相形见绌.)你能看到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  

您可能会注意到两个调用实际上都是ulong通过引用传递父值的实例- 这两个示例在这方面都是相同的.父节点指示其私有副本ul驻留在上层堆栈帧中的地址.事实证明,没有必要让被调查者不会阅读他们撒谎的那些实例,只要我们可以确定他们从不写那些指针.这是一个"懒"或延迟的方法,其分配给每个下(子)堆栈帧中用于保存责任的ValueType语义其较高的向上呼叫者.ValueType如果孩子永远不会覆盖它,则不需要呼叫者主动复制传递给子帧的任何子帧; 为了尽可能地避免不必要的复制,只有孩子可以做出最新的决定.

同样有趣的是,我们可能会在这里解释rax我在第一个"ByVal"示例中的笨拙使用.通过内联完全减少了按值方法之后,为什么还需要在寄存器中进行旋转？

在这些最新的两个完整方法体版本中,它清楚第一个方法返回ulong,第二个方法返回void.由于传入了返回值rax,因此ByVal方法无论如何都必须将其提取到该寄存器中,因此在那里旋转它也是明智之举.因为ByRef方法不需要返回任何值,所以它不需要在任何地方为其调用者添加任何内容,更不用说了rax.似乎"不必费心rax"解放了ByRef代码以ulong将其父级共享的实例定位为"它所在的位置",使用花式qword ptr间接进入父级的堆栈帧内存,而不是使用寄存器.对于rax我们之前看到的"剩余"谜团,这是我的推测,但也许是可信的解释.

Answer 4

转移的天真版本将无效.原因是,右移有符号数字将用符号位填充左边的位,而不是0:

您可以通过以下方式验证此事实

Console.WriteLine(-1 >> 1);

正确的方法是:

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 5

对于使用 .NET Core 3.0 或 .NET 5.0 及更高版本的用户，可以使用BitOperations.RotateLeft和RotateRight。