Arbitrarily Shift Bit Array Represented As Array of 32-bit Integers

Question

Given an array of 32-bit integers which represent a bit array, shift the values by a specified amount in either direction. Positive shifts go to the left and negative values go to the right. This is a bit array so bits should wrap across values in the array.

For example, given the following data:

a[2] = 11110000 11110000 11110000 11110000
a[1] = 11110000 11110000 11110000 11110000
a[0] = 11110000 11110000 11110000 11110000 <-- 0th bit

Shifting the original by 2 should result in:

a[3] = 00000000 00000000 00000000 00000011
a[2] = 11000011 11000011 11000011 11000011
a[1] = 11000011 11000011 11000011 11000011
a[0] = 11000011 11000011 11000011 11000000 <-- 0th bit

Shifting the original by -3 should result in:

a[2] = 00011110 00011110 00011110 00011110
a[1] = 00011110 00011110 00011110 00011110
a[0] = 00011110 00011110 00011110 00011110 <-- 0th bit

There's no restriction on shift amount (i.e., can be greater than 32) so be mindful of where your bits are going!

Here's the method signature:

int[] bitArrayShift(int[] bits, int shift)

Implementations should:

• Return an array whose contents represented the original bit array's contents shifted by the supplied number.
• Return an array whose size is the minimum amount required to hold the values after the shift. You should not wrap back around to the 0th bit but rather expand to hold it.
• Not mutate the input array. It should be treated as being passed by reference (therefore having mutable contents). Basically, don't put any new values at any position in the input array.

The following assertion should always return true for any value of 'bit' and 'shift':

// Given 'originalBits' as incoming bit array.
// Given 'bit' as a number between [0, originalBits.length * 32).
// Given 'shift' as any integer value.

// Get the value in the array at the index of 'bit'
bool original = ((originalBits[bit / 32] & (1 << (bit % 32)) != 0
// Shift the original bits by the specified 'shift'
int[] shiftedBits = bitArrayShift(originalBits, shift)
// Offset the original 'bit' by the specified 'shift'
int shiftedBit = bit + shift
// Get the value in the shifted array at the index of 'shiftedBit'
bool shifted = ((shiftedBits[shiftedBit / 32] & (1 << (shiftedBit % 32)) != 0
// They should be equal.
assert original == shifted

Smallest character count wins. Count method body contents ONLY sans leading and trailing whitespace. That is, the method declaration up to and including the block start (if any) and ending exclusively at the block end (if any).

E.g., for Java:

public static int[] shiftBitArray(int[] bits, int shift) {
  << COUNT THIS ONLY >>>
}

Answer 1

Java 306

public static int[] shiftBitArray(int[] bits, int shift) {
    BigInteger r = BigInteger.ZERO;
    for (int i = bits.length - 1; i >= 0;) r = BigInteger.valueOf(0xffffffffL & bits[i--]).or(r.shiftLeft(32));
    r = r.shiftLeft(shift);
    int[] a = new int[(int) Math.ceil(r.bitLength() / 32d)];
    for (int i = 0; i < a.length; r = r.shiftRight(32)) a[i++] = r.intValue();
    return a;
}

Answer 2

Java 500

public static int[] shiftBitArray(int[] bits, int shift) {
  int t = 32, w;
  long x = 1L << t;
  String s = "", z = Long.toString(x, t / 2).substring(1); z += z; z += z;
  for (int i : bits) s = Long.toString(i & x - 1 | x, 2).substring(1) + s;
  for (; shift > 0; shift -= t) s += z;
  s = -shift > s.length() ? z : z.substring(shift & t - 1) + s.substring(0, s.length() + shift);
  while (s.startsWith(z)) s = s.substring(t);
  int[] r = new int[(w = s.length()) / t];
  for (int j = 0; j < r.length; j++) r[j] = (int) Long.parseLong(s.substring(w -= t, w + t), 2);
  return r;
}

Answer 3

Python (181)

def bitArrayShift(b, s):
 a=''.join(bin(x)[2:].zfill(32)for x in b)
 a=(a+'0'*s if s>0 else a[:s]).lstrip('0')
 return[int(a[b:c],2)for b,c in[(x-32if x>31 else 0,x)for x in range(len(a),0,-32)]][::-1]or[0]

It basically just turns the array into a single string of bits, rotates by string manipulation and converts it back to integers.

Answer 4

GolfScript, 32 characters

{{2.5??base}:^~2@.0>{?*}{~)?/}if^}:S;

(Character count without {}:S; as specified in the question) Defines a function S with works on the stack (there is no such thing like call by reference for stack-based languages). Usage:

2 [4042322160 4042322160 4042322160] S p    # => [3 3284386755 3284386755 3284386752]
-3 [4042322160 4042322160 4042322160] S p   # => [505290270 505290270 505290270]

6 characters more if one prefers lowest-word first.

Answer 5

J (32)

shift=:4 :'#.|."1|._32>\|.({.~x+#);y#:~32#2'

(Not counting the shift=:4 :'...'.)

Test:

   9!:11[20 NB. set print precision high enough for the large numbers to show

   shift=:4 :'#.|."1|._32>\|.({.~x+#);y#:~32#2'
   2 shift 4042322160 4042322160 4042322160
3 3284386755 3284386755 3284386752
   _3 shift 4042322160 4042322160 4042322160
505290270 505290270 505290270

Explanation:

• y#:~32#2: encode each value in y as 32 bits, giving a matrix.
• ;: join the rows of the matrix together, giving a list of bits.
• {.~x+#: take the first x+length elements from the list, padding with zeroes. (so zeroes get added to the end if x is positive, dropped if x is negative.)
• |.: flip the list (to make partitioning easier)
• _32>\: group the bits into groups of 32, padding with zeroes. (the extra zeroes go on the end, which is why the list had to be flipped.)
• |."1|.: flip the resulting matrix both horizontally and vertically, putting the bits back in the right order.
• #.: decode each line of bits back into an integer.

Answer 6

Scala 324

def shiftBitArray(bits: Array[Int], shift: Int): Array[Int] = {
    def f(i:Array[Int])=i.map(x => String.format("%32s",x.toBinaryString).replace(' ','0')).mkString
    def g(x:Int)=List.fill(x)("0").mkString
    def h(s:String)=s.grouped(32).toArray.map(x=>java.lang.Long.parseLong(x, 2).toInt)
    val s=shift
    if (s<=0)h(g(-1*s)+f(bits).dropRight(-1*s))
    else h(g(32-s)+f(bits)+g(s))
}

Answer 7

APL, 49

shift←{⌽2⊥⍉(c,32)⍴⌽(32×c←⌈n÷32)↑⌽(n←⍺+⍴v)↑v←∊(32/2)∘⊤¨⌽⍵}

Could probably be golfed some more. The entire (32×⌈n÷32)↑ and the following reshaping is probably overkill.

Examples

      0 shift 3/4042322160
4042322160 4042322160 4042322160
      2 shift 3/4042322160
3284386752 3284386755 3284386755 3
      ¯3 shift 3/4042322160
505290270 505290270 505290270

Answer 8

Golfscript (57)

A first draft, slightly longer than APL but all ascii. Probably possible to golf a little more.

~.~)@2 32?:q;{\q*+}*@{2*}*\{2/}*{q%1$}{;q/}/\;-1%.![0]*+p

Answer 9

Mathematica 57

In infix form:

a_~f~n_ := Flatten@a~RotateLeft~n~ArrayReshape~Dimensions@a

In standard prefix form:

f[a_,n_]:=ArrayReshape[RotateLeft[Flatten[a], n], Dimensions[a]]

where a is the array and n is the shift parameter.

---

Flatten transforms a into a list of integers.

RotateLeft[list,n] rotates list n places leftward (if >= 0) or rightward (if n<0).

Dimensions obtains the dimensions of the input matrix.

ArrayReshape[list, Dimensions[a]] transforms list into an array with the dimensions of the original matrix, a.

RotateRight[a,n] has the same effect as RotateLeft[a,-n] for all integers n.