Circular shift an arbitrary byte-array bitwise

Question

Given an arbitrary array of octets, and an offset measured in bits, the goal is to bitwise left rotate the array by the specified number of bit positions as if the entire array were a single contiguous number. Byte order is big-endian.

As an example, given the (not zero terminated) ASCII string abcd and a shift of 5 bits. we turn this array of bytes:

01100001 01100010 01100011 01100100

into this one:

00101100 01001100 01101100 10001100

Notice that the bits propagate to the left from byte to byte and that they wrap back around.

Now that I think you've all got the idea, the rules:

• Your program should accept an arbitrary unsigned integer ("number of bits to shift" non-negative, possibly zero, limited only by the size of the standard integer type) and a raw stream of octets of arbitrary length (you may assume the length is strictly positive). How you accept these is up to you (file,stdin,parameter are all acceptable). Your program should output the shifted bytes in an analogous manner (i.e. file,stdout,return value).
• "Cut-and-paste" style code is not allowed. That is, you can't rely on your user to set the value of a certain variable before calling your code.
• The byte ordering is big-endian.
• Shortest code wins.

EDIT: It's clear now I should have restricted the input output format a bit more. The solutions that are using ASCII 0s and 1s directly aren't very interesting unfortunately.

Answer 1

APL (1)

it's a builtin

      5⌽0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 0 0
0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 0 0 0 1 1 0 0

Answer 2

C 89

Shifting is done in-place in *s array. l is array length and f is number of bits to shift.

void f(char*s,l,f){while(f--)for(int i=0,j,c=*s<0;s[j=i++]<<=1,s[j]+=i%l?s[i]<0:c,i<l;);}

Answer 3

Sed, 35 bytes

:a
s/1-\(.\)\(.*\)/-\2\1/
ta
s/.//

Takes input on stdin, as number of bits to shift by in unary, followed by -, followed by the binary stream, without spaces. e.g.

echo 11111-01100001011000100110001101100100 | sed -f a.sed

outputs

00101100010011000110110010001100

Answer 4

Perl, 33 (32 + 1 for -p)

1while(s/1-(.)(.*)/-$2$1/);s/.//

Takes input on stdin, as number of bits to shift by in unary, followed by -, followed by the binary stream, without spaces. e.g.

echo 11111-01100001011000100110001101100100 | perl -pe '1while(s/1-(.)(.*)/-$2$1/);s/.//'

Answer 5

APL (23)

{2⊥⍉(8,⍨⍴⍵)⍴⍺⌽,⍉⍵⊤⍨8/2}

This is a function that takes the rotation as its left argument and the byte array as its right argument (as numbers).

      5{2⊥⍉(8,⍨⍴⍵)⍴⍺⌽,⍉⍵⊤⍨8/2}97 98 99 100
44 76 108 140

Answer 6

C, 142 bytes

It's huge :(

Input is taken from parameters, puts shifted string to stdout.

main(int d,char**v){d=strtoul(v[1],0,10);while(d--){v[1]=v[2]+1;**v=*v[2];strcpy(v[2],v[1]);while(*(v[1]++));*v[1]--=0;*v[1]=**v;}puts(v[2]);}

Answer 7

Python, 43 42 bytes

Takes shifts and data from stdin, returns shifted data in stdout. Input format is <shift_amount>\n<data>

a=-input();b=raw_input();print b[a:]+b[:a]

Answer 8

q (18)

depending on how picky you are about exact output format and launch, i can get it down to 18 in q:

$ ls -l shift*.q
-rw-r--r-- 1 daviaaro ccM504 19 Jan  8 16:05 shift1.q
-rw-r--r-- 1 daviaaro ccM504 22 Jan  8 16:07 shift2.q
-rw-r--r-- 1 daviaaro ccM504 25 Jan  8 16:07 shift3.q
$ cat shift1.q
(rotate)."I*"$.z.x
$ q shift1.q 5 "01100001011000100110001101100100" <&-
"00101100010011000110110010001100"
$ cat shift2.q
-1(rotate)."I*"$.z.x;
$ q shift2.q 5 01100001011000100110001101100100 <&-
00101100010011000110110010001100
$ cat shift3.q
-1(rotate)."I*"$.z.x;
\\
$ q shift3.q -q 5 01100001011000100110001101100100
00101100010011000110110010001100
$ 

of course, it helps that the actual function happens to be in the standard lib :)

all three interpret two command-line args as int and string and rotate the string by the int

the first case just shows the string representation of the string (a (mostly) pasteable notation)

the second and third cases print it

in the first two cases, i'm relying on q to quit itself when run without stdin

the third case has an explicit quit command (and an extra command-line arg to suppress the REPL welcome message, which is automatically suppressed in the other cases due to stdin being closed)

note btw that the byte counts from ls include newlines, even on the two one-line files, and since q is fine with code files that are missing their last newline, the actual counts are 18, 21, and 24

ETA:

how do you feel about this?

$ q<<<'5 rotate 01100001011000100110001101100100b'
00101100010011000110110010001100b
$ 

is it valid? how would you count it? (the b is q's notation for a binary vector/bitstring. if you prefer, it would also work on the string version at the cost of an extra character)

Answer 9

C# (210)

void r(byte[] a, int n){string s="";for(int i=0;i<a.Length;i++)s+=Convert.ToString(a[i],2).PadLeft(8,'0');s=s.Substring(n)+s.Substring(0,n);for(int i=0;i<a.Length;i++)a[i]=Convert.ToByte(s.Substring(i*8,8),2);}

This is a function 'r' in C# that takes a byte[] and an integer n. It does in-place rotation, so the original array is rotated, and nothing is returned.

I convert the byte array to string of bits, rotate, and convert back to bytes. It seems like a cheat, but the requirements does not prevent it.

The pretty code is following:

void r(byte[] a, int n)
{
    string s = "";
    for (int i = 0; i < a.Length; i++)
        s += Convert.ToString(a[i], 2).PadLeft(8, '0');

    s = s.Substring(n) + s.Substring(0, n);

    for (int i = 0; i < a.Length; i++)
        a[i] = Convert.ToByte(s.Substring(i * 8, 8), 2);
}