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 2021
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 2021
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 2021
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 2021
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 2021
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 2021
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 2021
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 2021