How to rotate right and left over an arbitrary number of bits. So say I am looking at 5 bits. How do I rotate around 5 bits, though I am in JavaScript. Or 8 bits, rol should convert the left-8-most bit to the 1 index position, and the right 1 bit should go to the left one. Etc.
Standard rol/ror functions don't work, in JavaScript it expands the number size.
function rol(word, shift, size) {
return (word << shift) | (word >> (size - shift));
}
function ror(word, shift, size) {
return (word >> shift) | (word << (size - shift));
}
For example, I am doing [2 ** 8, 2 ** 9 - 1], those are all 8-bit values. Now I want to rotate them to generate de Bruijn graphs, but the rotation functions I am used to are not the appropriate tool.
I am getting this for n rol ror: 101100000 1011000010 1011000010110000.
I expect to get 101100000 011000001 010110000.
I would like to be able to to do this for any sized integer from 2-bits to 64 bits.
Basically something like this, but with bit manipulation techniques instead of converting to string:
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
}
CodePudding user response：
You need to properly mask your sub results to throw away overlapping bits. Also note that <<,>> behavior is platform dependent so to avoid undefined behavior and logical collisions add proper masks...
I see it like this (in 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));
}
//---------------------------------------------------------------------------
Where bits is the number of bits you want to have/emulate, shift is number of bits to shift (like x<<shift or x>>shift in C ) ...
Continuous 11 bit shift by 1 bit (rol on left, ror on right) for 1111011b:
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
The same for 2 bit shift:
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
Tested in VCL like this:
//---------------------------------------------------------------------------
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);
}
}
//-------------------------------------------------------------------------
I just tweaked bitshifts from my ALU32 from here:
to match your case...
[Notes]
In case shift is big you should add shift%=bits to both functions. Also if shift is negative use the other function ...
//---------------------------------------------------------------------------
#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));
}
//---------------------------------------------------------------------------