如何在任意大小的数字范围内按位向左旋转和向右旋转？

Question

如何在任意位数上左右循环。所以说我正在看 5 位。尽管我在 JavaScript 中，但如何旋转 5 位。或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位的值。现在我想旋转它们来生成de Bruijn图，但是我习惯的旋转函数不是合适的工具。

我正在为 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 是您要 have/emulate 的位数，shift 是要移动的位数（如 x<<shift 或 x>>shift C++) ...

对于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 的位移位：

Can't make value propagate through carry

以符合您的情况...

备注

如果 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));
    }
//---------------------------------------------------------------------------

如何在任意大小的数字范围内按位向左旋转和向右旋转？

How to bitwise rotate left and rotate right on arbitrary sized number ranges?

algorithm

math

bit-manipulation

备注