6
\$\begingroup\$

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 >>>
}
\$\endgroup\$

closed as unclear what you're asking by cat, mbomb007, Rɪᴋᴇʀ, Alex A. Apr 26 '16 at 22:58

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ "therefore having mutable contents". What exactly does this mean? Did you mean immutable? \$\endgroup\$ – Justin Jan 25 '14 at 5:14
  • \$\begingroup\$ Should leading zeroes be stripped (ie is [1][0] an allowed result instead of just [1]? \$\endgroup\$ – Joachim Isaksson Jan 25 '14 at 13:45
  • \$\begingroup\$ Your example of shifting the original array by 2 does not wrap across values in the array. It augments the array thereby changing its dimensions. Isn't this incorrect? \$\endgroup\$ – DavidC Jan 25 '14 at 17:44
  • \$\begingroup\$ The question does not completely define how wrapping occurs in the negative direction. What is the result of shifting by -5? Assuming the intention is to prepend a new index at the beginning, similarly to the second example which appended a new index. \$\endgroup\$ – James Wald Jan 25 '14 at 21:09
2
\$\begingroup\$

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

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ You can save ~100 characters by removing whitespace: 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; \$\endgroup\$ – Justin Jan 25 '14 at 5:31
  • 1
    \$\begingroup\$ Some other big character savers: change the first line to int t=32,w,d=shift,b[]=bits; and refer to shift as d and bits as b. Rather than using Long.toString(), use x.toString(). Rather than s.length() twice, use int l=s.length() and refer to s.length() as l. Rather than z+=z;z+=z, use z+=z+z;. Additionally, your 1L at the beginning can be just 1. You might also considering substituting the constant values instead of t, since t is never assigned anything other than 32 \$\endgroup\$ – Justin Jan 25 '14 at 6:05
  • \$\begingroup\$ Via my suggestions(minus some that actually harm), I got it down to 376 characters. Might be able to remove the int at the beginning altogether and simply move the long in place of the int, but I haven't checked it: int t=32,w,d=shift;long x=1<<t;String s="",z=x.toString(x,16).substring(1);z+=z+z+z;for(int i:bits)s=x.toString(i&x-1|x,2).substring(1)+s;for(;d>0;d-=t)s+=z;int l=s.length();s=-d>l?z:z.substring(d&31)+s.substring(0,l+d);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)x.parseLong(s.substring(w-=t,w+t),2);return r; \$\endgroup\$ – Justin Jan 25 '14 at 6:11
  • 2
    \$\begingroup\$ Because this is code-golf, go for compact. \$\endgroup\$ – Justin Jan 25 '14 at 6:13
  • 1
    \$\begingroup\$ Can do 350 with great sacrifice to cuteness. int t=32,w=shift,a,y;long x=1L<<t;String s="",z="00000000";z+=z+z+z;for(int i:bits)s=Long.toString(i&x-1|x,2).substring(1)+s;for(;w>0;w-=t)s+=z;y=s.length();for(s=-w>y?z:z.substring(w&31)+s.substring(0,y+w);s.startsWith(z);)s=s.substring(t);w=s.length();a=w/t;int[] r=new int[a];for(y=0;y<a;)r[y++]=(int) parseLong(s.substring(w-=t,w+t),2);return r; \$\endgroup\$ – Jesse Wilson Jan 25 '14 at 6:51
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

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

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

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

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.

\$\endgroup\$

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