# Circular shift an arbitrary byte-array bitwise

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.

• 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? Commented Jan 8, 2014 at 15:32
• One of those questions is already answered, but I will clarify. Commented Jan 8, 2014 at 15:33
• @PeterTaylor better? Commented Jan 8, 2014 at 15:40
• Does it need to be a complete program? Commented Jan 8, 2014 at 16:25
• I just want to ask why byte order matters?
– tia
Commented Jan 8, 2014 at 16:56

## 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;);}


# C#, 321308 304 bytes

var y=System.Text.Encoding.UTF8.GetBytes(args[1]).ToList();int i=int.Parse(args[0]),m,j=0;for(;i>7;y.RemoveAt(0),i-=8)y.Add(y[0]);byte c=0,u;for(m=8-i;j<y.Count;j++){u=(byte)((255<<m&y[j])>>m);if(j<1)c=u;y[j]<<=i;if(j>0)y[j-1]|=u;}y[^1]|=c;Console.Write(System.Text.Encoding.UTF8.GetString(y.ToArray()));


Dropped 13 bytes thanks to awesome suggestions from Kevin, and another 4 bytes with suggestions from ceilingcat!

Uncompressed version below. This uses C# v9 top-level statements feature, so the program below compiles into an executable. Program expects two arguments: bits and bytes in a form of a UTF8 string (e.g., execute is as ./program 5 abcd).

// get bytes from the provided provided (assumed in UTF8)
var y = System.Text.Encoding.UTF8.GetBytes(args[1]).ToList();
int i = int.Parse(args[0]), m, j = 0; // i - how many bits to shift

// rotate full bytes first if bits >= 8
for (; i > 7; y.RemoveAt(0), i -= 8) // drop the first byte
y.Add(y[0]); // append first byte to the end

byte c = 0, u; // c keeps the bits to wrap around from first byte to the last
// u will be used to shift bits between neighboring bytes

// now i < 8 guaranteed
for (m = 8 - i; j < y.Count; j++)
{
u = (byte) ((255 << m & y[j]) >> m); // bits to shift
if (j < 1) c = u; // if we are on the first byte, store them in c
y[j] <<= i; // shift the byte
if (j > 0) y[j - 1] |= u; // shift the cutoff bits to prev byte
// if current byte is not the first byte
}

y[^1] |= c; // wrap around the bits

// and output
Console.Write(System.Text.Encoding.UTF8.GetString(y.ToArray()));

• Welcome to Code Golf, and nice first answer! Be sure to check out our Tips for golfing in C# page for ways you can golf your program! You might want to add a TIO link or similar so others can test your code online. Commented Feb 18, 2022 at 8:51
• @emanresuA Thanks! TIO's C# does not seem to support C#'s top-level statements and I couldn't find an online C# compiler that supports command line arguments... Commented Feb 18, 2022 at 9:07
• while(i>7){y.Add(y[0]);y.RemoveAt(0);i-=8;} can be for(;i>7;y.RemoveAt(0),i-=8)y.Add(y[0]); for -3 and var i=int.Parse(args[0]) + var m=8-i;byte c=0,u;for(var j=0; can be int i=int.Parse(args[0]),m,j=0;byte c=0,u;for(m=8-1; for another -6. And if there isn't an online compiled for C# 9+, you could put the args in the header on TIO (and replace ^1 with y.Count-1, since TIO is below C# v8 apparently): try it online. Oh, and welcome to CGCC. :) Commented Feb 18, 2022 at 10:03
• You can also golf the WriteLine to Write for another -4. (And apparently the Visual C# Online Compiler uses Args for the same behavior as args, so you could actually save an additional byte by using Visual C# Interactive Compiler as language and sacrificing ^1 to y.Count-1 to remove Console. for -1: try it online. But if you prefer to use standard C# with ^1 and top-level arguments I can understand.) Commented Feb 18, 2022 at 10:19
• Thanks @ceilingcat for some great suggestions! Another 4 bytes off! Commented Feb 21, 2022 at 4:42

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


## 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/.//'

• 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. Commented Jan 8, 2014 at 16:48
• @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. Commented Jan 8, 2014 at 16:52

# 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


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


# 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]);}


# 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]

• 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. Commented Jan 9, 2014 at 21:23
• @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>. Commented Jan 9, 2014 at 22:59
• You've shifted bytewise. Not bitwise. Huge difference here. Commented Jan 12, 2014 at 0:21

# 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)

• 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. Commented Jan 9, 2014 at 21:08
• 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. Commented Jan 9, 2014 at 21:18
• 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? Commented Jan 9, 2014 at 21:31
• 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 Commented Jan 9, 2014 at 21:35
• 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. Commented Jan 10, 2014 at 10:26

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 = 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);
}

• As long as it works, you can do it however you want. Efficiency isn't required in code-golf. Commented Jan 8, 2014 at 16:42

# Python 3, 40 Bytes

s,n=open(0);print(n[int(s):]+n[:int(s)])


Try It Online!

This is basically a port of Oberons answer, and takes the same input from stdin as his Python 2 solution:

in:
5
01100001011000100110001101100100
out:
00101100010011000110110010001100


this is also my first post on this site, happy to be here!

• Welcome to the site. Commented Feb 21, 2022 at 15:47