41

_rotlC++ 的 C# 等价物(.NET 2.0) 是_rotr什么?

4

7 回答 7

49

这是你想要做的吗?

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

基本上你想要的是

(左)

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

或者

(右)

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

此外,正如 Mehrdad 已经建议的那样,这仅适用于 uint,这也是 Jon 给出的示例。

于 2009-05-01T16:10:40.840 回答
25

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 指出的,有符号整数的右移 ( >>) 是一个特性:它用符号位填充 MSB,而不是像无符号数那样用 0 填充。我现在更改了获取和返回uint(无符号 32 位整数)的方法——这也更符合 C++rotlrotr函数。如果你想旋转整数,只需在传递之前对它们进行大小写,然后再次转换返回值,当然。

示例用法:

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

(注意,int.MinValue二进制是 111111111111111111111111 - 32 1s。)

于 2009-05-01T16:08:49.487 回答
16

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

这很好地简化了旋转函数,并消除了一类常见的错误,即您忘记重新存储函数的返回值,但同时可能引入一种新的、完全不同类型的错误——当您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程序运行

为了演示按引用扩展方法的使用,我将只关注上面显示的第一个方法“向左旋转”,并比较传统按值扩展方法和较新的按引用方法之间的 JIT 输出。以下是要在 Windows 10 上的.NET 4.7中的x64 版本上比较的两种测试方法。如上所述,这将使用“未抑制”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指令几乎不是问题。jitter 能够看穿我们的一堆 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的完全独立的值覆盖值“x”的父副本的过程。ulongrax

现在让我们看看被调用的目标函数的代码。看到它们需要强制 JIT “抑制”优化。以下是 x64 Release JIT 为Rol_ByValRol_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所以这是我对“剩余”的推测,但也许是可信的解释

于 2018-02-02T10:17:48.253 回答
11

简单的换档版本是行不通的。原因是,右移有符号数将用符号位填充左边的位,而不是 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)((val >> count) | (val << (32 - count)));
}
于 2009-05-01T16:18:38.763 回答
4

对于使用 .NET Core 3.0 或 .NET 5.0 及更高版本的用户,可以使用BitOperations.RotateLeftRotateRight.

于 2020-12-11T13:21:59.470 回答
3

请注意,如果要创建对较短整数值进行操作的重载,则需要添加一个额外的步骤,如下所示:

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

32 位和 64 位重载不需要屏蔽操作,因为移位运算符本身会处理这些大小的左侧操作数。

于 2012-09-26T23:57:03.573 回答
-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);
于 2014-09-10T06:55:52.687 回答