如何在任意大小的数字范围上向左和向右旋转?

Question

如何在任意数量的位上左右旋转。假设我在看5个比特。我如何旋转5位，虽然我在JavaScript。或者8位，rol应该将最左边的8位转换为第1个索引位置，而右边的1位应该转换为最左边的1位。等。

标准的rol/ror函数不起作用，在JavaScript中它扩展了数字的大小。

function rol(word, shift, size) {
return (word << shift) | (word >> (size - shift));
}
function ror(word, shift, size) {
return (word >> shift) | (word << (size - shift));
}

例如，我在做[2 ** 8, 2 ** 9 - 1]，这些都是8位值。现在我想旋转它们来生成德布鲁因图，但是我习惯的旋转函数并不是合适的工具。

我得到这个n rol ror:101100000 1011000010 1011000010110000。

我期望得到101100000 011000001 010110000。

我希望能够对从2位到64位的任何大小的整数执行此操作。

基本上是这样的，但使用了位操作技术，而不是转换为字符串:

function rol(n, size) {
const bits = n.toString(2).padStart(size, 0).split('').reverse()
const left = bits.pop()
bits.unshift(left)
const string = bits.reverse().join('')
const number = parseInt(string, 2)
return number
}
function ror(n, size) {
const bits = n.toString(2).padStart(size, 0).split('').reverse()
const right = bits.shift()
bits.push(right)
const string = bits.reverse().join('')
const number = parseInt(string, 2)
return number
}

Answer 1

您需要适当地屏蔽子结果以丢弃重叠的位。还要注意<<,>>行为依赖于平台，因此要避免未定义的行为和逻辑冲突，请添加适当的掩码…

我是这样看的(c++):

//---------------------------------------------------------------------------
#ifndef _WINDEF_
typedef unsigned __int32 DWORD; // define DWORD if windows header not present
#endif
//---------------------------------------------------------------------------
DWORD rol(DWORD x,int shift,int bits)
{
// masks                           |       bits        |
DWORD m0=(1<<(bits-shift))-1;   // |0000000|11111111111|
// | shift |           |
DWORD m1=(1<<shift)-1;          // |00000000000|1111111|
// |           | shift |
return ((x&m0)<<shift) | ((x>>(bits-shift))&m1);
}
//---------------------------------------------------------------------------
DWORD ror(DWORD x,int shift,int bits)
{
// masks                           |       bits        |
DWORD m0=(1<<(bits-shift))-1;   // |0000000|11111111111|
// | shift |           |
DWORD m1=(1<<shift)-1;          // |00000000000|1111111|
// |           | shift |
return ((x>>shift)&m0) | ((x&m1)<<(bits-shift));
}
//---------------------------------------------------------------------------

其中bits是您想要/模拟的位数，shift是要移位的位数(如c++中的x<<shift或x>>shift)…

1111011b连续11位移位1位(左为rol，右为ror):

10987654321098765432109876543210  10987654321098765432109876543210
--------------------------------  --------------------------------
00000000000000000000000001111011b 00000000000000000000000001111011b
00000000000000000000000011110110b 00000000000000000000010000111101b
00000000000000000000000111101100b 00000000000000000000011000011110b
00000000000000000000001111011000b 00000000000000000000001100001111b
00000000000000000000011110110000b 00000000000000000000010110000111b
00000000000000000000011101100001b 00000000000000000000011011000011b
00000000000000000000011011000011b 00000000000000000000011101100001b
00000000000000000000010110000111b 00000000000000000000011110110000b
00000000000000000000001100001111b 00000000000000000000001111011000b
00000000000000000000011000011110b 00000000000000000000000111101100b
00000000000000000000010000111101b 00000000000000000000000011110110b
00000000000000000000000001111011b 00000000000000000000000001111011b

2位移位相同:

10987654321098765432109876543210  10987654321098765432109876543210
--------------------------------  --------------------------------
00000000000000000000000001111011b 00000000000000000000000001111011b
00000000000000000000000111101100b 00000000000000000000011000011110b
00000000000000000000011110110000b 00000000000000000000010110000111b
00000000000000000000011011000011b 00000000000000000000011101100001b
00000000000000000000001100001111b 00000000000000000000001111011000b
00000000000000000000010000111101b 00000000000000000000000011110110b
00000000000000000000000011110110b 00000000000000000000010000111101b
00000000000000000000001111011000b 00000000000000000000001100001111b
00000000000000000000011101100001b 00000000000000000000011011000011b
00000000000000000000010110000111b 00000000000000000000011110110000b
00000000000000000000011000011110b 00000000000000000000000111101100b
00000000000000000000000001111011b 00000000000000000000000001111011b
00000000000000000000000111101100b 00000000000000000000011000011110b
00000000000000000000011110110000b 00000000000000000000010110000111b
00000000000000000000011011000011b 00000000000000000000011101100001b
00000000000000000000001100001111b 00000000000000000000001111011000b
00000000000000000000010000111101b 00000000000000000000000011110110b
00000000000000000000000011110110b 00000000000000000000010000111101b
00000000000000000000001111011000b 00000000000000000000001100001111b
00000000000000000000011101100001b 00000000000000000000011011000011b
00000000000000000000010110000111b 00000000000000000000011110110000b
00000000000000000000011000011110b 00000000000000000000000111101100b
00000000000000000000000001111011b 00000000000000000000000001111011b

在VCL中测试如下:

//---------------------------------------------------------------------------
AnsiString dec2bin(DWORD x)
{
AnsiString s;
int i;
s.SetLength(33);
for (i=0;i<32;i++,x>>=1) s[32-i]='0'+(x&1);
s[33]='b';
return s;
}
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner)
{
int i;
DWORD x=123,y=x;
mm_log->Lines->Add("10987654321098765432109876543210  10987654321098765432109876543210");
mm_log->Lines->Add("--------------------------------  --------------------------------");
for (i=0;i<32;i++)
{
mm_log->Lines->Add(dec2bin(x)+" "+dec2bin(y));
x=rol(x,2,11);
y=ror(y,2,11);
}
}
//-------------------------------------------------------------------------

我只是从这里调整了ALU32的位移:

• 不能让值通过进位传播

指出

如果shift很大，则应将shift%=bits添加到两个函数中。如果shift是负的，使用另一个函数…

//---------------------------------------------------------------------------
#ifndef _WINDEF_
typedef unsigned __int32 DWORD; // define DWORD if windows header not present
#endif
//---------------------------------------------------------------------------
DWORD rol(DWORD x,int shift,int bits);
DWORD ror(DWORD x,int shift,int bits);
//---------------------------------------------------------------------------
DWORD rol(DWORD x,int shift,int bits)
{
if (shift<0) return ror(x,-shift,bits);
shift%=bits;
// masks                           |       bits        |
DWORD m0=(1<<(bits-shift))-1;   // |0000000|11111111111|
// | shift |           |
DWORD m1=(1<<shift)-1;          // |00000000000|1111111|
// |           | shift |
return ((x&m0)<<shift) | ((x>>(bits-shift))&m1);
}
//---------------------------------------------------------------------------
DWORD ror(DWORD x,int shift,int bits)
{
if (shift<0) return rol(x,-shift,bits);
shift%=bits;
// masks                           |       bits        |
DWORD m0=(1<<(bits-shift))-1;   // |0000000|11111111111|
// | shift |           |
DWORD m1=(1<<shift)-1;          // |00000000000|1111111|
// |           | shift |
return ((x>>shift)&m0) | ((x&m1)<<(bits-shift));
}
//---------------------------------------------------------------------------