2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What's the range of valid input? Can the shift be negative? Zero? Greater than or equal to the number of bits in the array? Can the array be of length zero? \$\endgroup\$ – Peter Taylor Jan 8 '14 at 15:32
  • \$\begingroup\$ One of those questions is already answered, but I will clarify. \$\endgroup\$ – Tim Seguine Jan 8 '14 at 15:33
  • \$\begingroup\$ @PeterTaylor better? \$\endgroup\$ – Tim Seguine Jan 8 '14 at 15:40
  • \$\begingroup\$ Does it need to be a complete program? \$\endgroup\$ – Hasturkun Jan 8 '14 at 16:25
  • \$\begingroup\$ Yes, that's clear now. Thanks. \$\endgroup\$ – Peter Taylor Jan 8 '14 at 16:29
1
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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;);}
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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/.//'
\$\endgroup\$
  • \$\begingroup\$ I can't find any rule you are breaking, although this isn't what I intended, since I didn't specify an encoding. Clever idea. \$\endgroup\$ – Tim Seguine Jan 8 '14 at 16:48
  • \$\begingroup\$ @Tim: I sort of took off from How you accept these is up to you, since the input was mostly unspecified. As an aside, this can take arbitrarily large shifts and bits. Also, taking the count in decimal would have made the sed version much longer. \$\endgroup\$ – Hasturkun Jan 8 '14 at 16:52
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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]);}
\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ Can you please describe the input format, since I don't know the exact semantics of input and raw_input? I haven't used python in a while. \$\endgroup\$ – Tim Seguine Jan 9 '14 at 21:23
  • \$\begingroup\$ @Tim raw_input() fetches an input line from stdin (sys.stdin.readline()) and removes \n. input() does the same but eval()s input before returning. Input format is thus <shift_amount>\n<data>. \$\endgroup\$ – Oberon Jan 9 '14 at 22:59
  • \$\begingroup\$ You've shifted bytewise. Not bitwise. Huge difference here. \$\endgroup\$ – boothby Jan 12 '14 at 0:21
1
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ The first one seems to break the requirement "Your program should output the shifted bytes in an analogous manner" in my opinion, since you accept input without quotes and return it with quotes. The second one seems to require the <&- on the commandline; that would have to be included in the character count. \$\endgroup\$ – Tim Seguine Jan 9 '14 at 21:08
  • \$\begingroup\$ And the -q flag counts as one extra character, so your counts from my point of view are: 21(but not valid), 24, and 25. Feel free to argue your case. Either of the second two answers are acceptable. \$\endgroup\$ – Tim Seguine Jan 9 '14 at 21:18
  • \$\begingroup\$ well, it sort of depends on the details. without the <&-, version two will still work, but the REPL will print a welcome banner and will remain open for interactive use after the program finishes. without the -q, version 3 will exit, but it will still print the welcome banner. if it matters, the welcome banner is printed to stderr, while the output is printed to stdout. would you consider any of those situations acceptable answers? \$\endgroup\$ – Aaron Davies Jan 9 '14 at 21:31
  • \$\begingroup\$ i'd like to note that the APL solution above doesn't seem to be getting charged for a newline . if we want to talk about solutions valid interactively rather than as code files, i have a full solution in six characters: rotate. :-p \$\endgroup\$ – Aaron Davies Jan 9 '14 at 21:35
  • \$\begingroup\$ Printing the banner to standard error is fine I guess. Keeping the REPL open is not. If I am keeping track then properly that means the last two solutions are both 24 then. \$\endgroup\$ – Tim Seguine Jan 10 '14 at 10:26
1
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ As long as it works, you can do it however you want. Efficiency isn't required in code-golf. \$\endgroup\$ – Tim Seguine Jan 8 '14 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.