www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Bit rotation question/challenge

reply burt <invalid_email_address cab.abc> writes:
I have a static array of `ubyte`s of arbitrary size:

```d
ubyte[4] x = [ // in reality, ubyte[64]
     0b00001000,
     0b00000001,
     0b00010101,
     0b11110010,
];
```

Now I want to bit-rotate the array as if it is one big integer. 
So:

```d
ubyte[n] rotateRight(size_t n)(ref const ubyte[n] array, uint 
rotation)
{
     // ?
}
// same for rotateLeft

ubyte[4] y = [
     0b11111001,
     0b00000100,
     0b00000000,
     0b10001010,
];
assert(x.rotateRight(9) == y);
assert(y.rotateLeft(9) == x);
```

Any ideas how this could be achieved? I.e. what should go at the 
"?" for rotateRight and rotateLeft?
Jan 30
next sibling parent reply Paul Backus <snarwin gmail.com> writes:
On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:
 I have a static array of `ubyte`s of arbitrary size:

 ```d
 ubyte[4] x = [ // in reality, ubyte[64]
     0b00001000,
     0b00000001,
     0b00010101,
     0b11110010,
 ];
 ```

 Now I want to bit-rotate the array as if it is one big integer.
You may find `std.bitmanip.BitArray` useful for this: http://phobos.dpldocs.info/std.bitmanip.BitArray.html
Jan 30
parent burt <invalid_email_address cab.abc> writes:
On Saturday, 30 January 2021 at 14:17:06 UTC, Paul Backus wrote:
 On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:
 [...]

 Now I want to bit-rotate the array as if it is one big integer.
You may find `std.bitmanip.BitArray` useful for this: http://phobos.dpldocs.info/std.bitmanip.BitArray.html
Thank you, this is indeed what I am looking for! For future reference, this is how I implemented it: ```d ubyte[n] rotateRight(size_t n)(ubyte[n] x, uint rotation) { import std.bitmanip : BitArray; ubyte[n] x2; foreach (i, value; x) // have to swap because of endianness x2[n - 1 - i] = value; auto copy = x2; auto bitArray1 = BitArray(cast(void[]) x2[], n * 8); auto bitArray2 = BitArray(cast(void[]) copy[], n * 8); bitArray1 >>= rotation; bitArray2 <<= n * 8 - rotation; bitArray1 |= bitArray2; foreach (i, value; x2) // swap back x[n - 1 - i] = value; return x; } ubyte[4] x = [ 0b00011000, 0b00100001, 0b00010101, 0b11110010, ]; writefln!"%(%8b,\n%)"(x.rotateRight(4)); ```
Jan 30
prev sibling parent reply Afgdr <zerzre.rertert gmx.com> writes:
On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:
 I have a static array of `ubyte`s of arbitrary size:

 ```d
 ubyte[4] x = [ // in reality, ubyte[64]
     0b00001000,
     0b00000001,
     0b00010101,
     0b11110010,
 ];
 ```

 Now I want to bit-rotate the array as if it is one big integer. 
 So:

 ```d
 ubyte[n] rotateRight(size_t n)(ref const ubyte[n] array, uint 
 rotation)
 {
     // ?
 }
 // same for rotateLeft

 ubyte[4] y = [
     0b11111001,
     0b00000100,
     0b00000000,
     0b10001010,
 ];
 assert(x.rotateRight(9) == y);
 assert(y.rotateLeft(9) == x);
 ```

 Any ideas how this could be achieved? I.e. what should go at 
 the "?" for rotateRight and rotateLeft?
cast as uint and shift. cast the result as ubyte[4].
Jan 30
parent reply Afgdr <zerzre.rertert gmx.com> writes:
On Saturday, 30 January 2021 at 14:40:49 UTC, Afgdr wrote:
 On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:
 I have a static array of `ubyte`s of arbitrary size:

 ```d
 ubyte[4] x = [ // in reality, ubyte[64]
     0b00001000,
     0b00000001,
     0b00010101,
     0b11110010,
 ];
 ```

 Now I want to bit-rotate the array as if it is one big 
 integer. So:

 ```d
 ubyte[n] rotateRight(size_t n)(ref const ubyte[n] array, uint 
 rotation)
 {
     // ?
 }
 // same for rotateLeft

 ubyte[4] y = [
     0b11111001,
     0b00000100,
     0b00000000,
     0b10001010,
 ];
 assert(x.rotateRight(9) == y);
 assert(y.rotateLeft(9) == x);
 ```

 Any ideas how this could be achieved? I.e. what should go at 
 the "?" for rotateRight and rotateLeft?
cast as uint and shift. cast the result as ubyte[4].
obiously, that works for n=4 with uint and n=8 for ulong, only.
Jan 30
parent reply burt <invalid_email_address cab.abc> writes:
On Saturday, 30 January 2021 at 14:41:59 UTC, Afgdr wrote:
 On Saturday, 30 January 2021 at 14:40:49 UTC, Afgdr wrote:
 On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:
 [...]
cast as uint and shift. cast the result as ubyte[4].
obiously, that works for n=4 with uint and n=8 for ulong, only.
Yes I used to do this, but then I needed it for n > 8.
Jan 30
next sibling parent Afgdr <zerzre.rertert gmx.com> writes:
On Saturday, 30 January 2021 at 14:56:14 UTC, burt wrote:
 On Saturday, 30 January 2021 at 14:41:59 UTC, Afgdr wrote:
 On Saturday, 30 January 2021 at 14:40:49 UTC, Afgdr wrote:
 On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:
 [...]
cast as uint and shift. cast the result as ubyte[4].
obiously, that works for n=4 with uint and n=8 for ulong, only.
Yes I used to do this, but then I needed it for n > 8.
As suggested in the other answer BitArray may be the best generic solution.
Jan 30
prev sibling parent vitamin <vit vit.vit> writes:
On Saturday, 30 January 2021 at 14:56:14 UTC, burt wrote:
 On Saturday, 30 January 2021 at 14:41:59 UTC, Afgdr wrote:
 On Saturday, 30 January 2021 at 14:40:49 UTC, Afgdr wrote:
 On Saturday, 30 January 2021 at 13:30:49 UTC, burt wrote:
 [...]
cast as uint and shift. cast the result as ubyte[4].
obiously, that works for n=4 with uint and n=8 for ulong, only.
Yes I used to do this, but then I needed it for n > 8.
You can try somethink like this: https://run.dlang.io/is/POQgnb import std.range : cycle, take, drop; import std.algorithm : copy; import std.stdio; version (LittleEndian) ubyte[n] rotateRight(size_t n)(ref const ubyte[n] array, uint rotation){ typeof(return) result; array[] .cycle() .drop(n - (rotation / 8) % n) .take(n) .copy(result[]); const ubyte bit_rotation = rotation % 8; enum ubyte full = 0b1111_1111; if(bit_rotation == 0) return result; ubyte next_prefix(const ubyte elm){ const ubyte suffix = (elm & ~(full << bit_rotation)); const ubyte prefix = cast(ubyte)(suffix << (8 - bit_rotation)); return prefix; } ubyte prefix = next_prefix(result[$-1]); foreach(ref ubyte elm; result[]){ const new_prefix = next_prefix(elm); elm = (elm >> bit_rotation) | prefix; prefix = new_prefix; } return result; } void main(){ ubyte[4] x = [ 0b00011000, 0b00100001, 0b00010101, 0b11110010, ]; writefln!"%(%8b,\n%)"(x.rotateRight(4)); }
Jan 30