_rotl
C++ 的 C# 等价物(.NET 2.0) 是_rotr
什么?
7 回答
这是你想要做的吗?
基本上你想要的是
(左)
(original << bits) | (original >> (32 - bits))
或者
(右)
(original >> bits) | (original << (32 - bits))
此外,正如 Mehrdad 已经建议的那样,这仅适用于 uint,这也是 Jon 给出的示例。
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++rotl
和rotr
函数。如果你想旋转整数,只需在传递之前对它们进行大小写,然后再次转换返回值,当然。
示例用法:
int foo1 = 8.RotateRight(3); // foo1 = 1
int foo2 = int.MinValue.RotateLeft(3); // foo2 = 4
(注意,int.MinValue
二进制是 111111111111111111111111 - 32 1s。)
使用最新的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”的父副本的过程。ulong
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
所以这是我对“剩余”的推测,但也许是可信的解释
简单的换档版本是行不通的。原因是,右移有符号数将用符号位填充左边的位,而不是 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)));
}
对于使用 .NET Core 3.0 或 .NET 5.0 及更高版本的用户,可以使用BitOperations.RotateLeft
和RotateRight
.
请注意,如果要创建对较短整数值进行操作的重载,则需要添加一个额外的步骤,如下所示:
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 位重载不需要屏蔽操作,因为移位运算符本身会处理这些大小的左侧操作数。
// 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);