c# - C#按位向左旋转和向右旋转

Question

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

score 49 · Accepted Answer

这是你想要做的吗？

基本上你想要的是

（左）

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

或者

（右）

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

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

score 25 · Accepted Answer

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。）

score 16 · Accepted Answer

使用最新的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_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所以这是我对“剩余”的推测，但也许是可信的解释

score 11 · Accepted Answer

简单的换档版本是行不通的。原因是，右移有符号数将用符号位填充左边的位，而不是 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)));
}

score 4 · Accepted Answer

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

score 3 · Accepted Answer

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

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 位重载不需要屏蔽操作，因为移位运算符本身会处理这些大小的左侧操作数。

score -4 · Accepted Answer

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

c# - C#按位向左旋转和向右旋转

7 回答 7

Related

Reference