title: Efficient concatenation of Bit Arrays Java
body: <p>I am currently writing a piece of code where I have identified that the concatenation of my two bit arrays is the bottleneck, and debating on how to make it more efficient. </p>
  
  <p>My Bit array is modelled as follows</p>
  
  <pre><code>public BitArray(int size) { 
      int sizeBytes = size / 8 ;
      if (size % 8 !=0) sizeBytes++;
      this.array = new byte[sizeBytes];
      this.size = size ; 
  }
  </code></pre>
  
  <p>where size is the size in bits.</p>
  
  <p>The challenge when concatenating two bit arrays efficiently is the straddling that needs to occur when concatenating a bit array of size 7 with one of size 6  for example. As such, 
  it is not possible to simply do two array copies.</p>
  
  <p>The solutions I am investigating, on top of what i currently have implemented is the following:
  compute the "straddle region" (the last 3 bits of a  5 bitarray for example). 
  copy the first array with system.array.copy
  manually set the 3 "straddling bits" from the second array using my setBit function.
  shift the second array by 3 to the left
  do a <code>System.arraycopy()</code></p>
  
  <p>Currently, I manually set each individual bit of the second array, as shown below.</p>
  
  <p>The issue is that with bit shifting,the operation is actually quite expensive given it has to be done for each byte, then the straddling has to occur again.</p>
  
  <p>Thoughts on how to improve the techniques outlined above?</p>
  
  <p>Here is the current code which performs poorly: </p>
  
  <pre><code>public static BitArray concatenate(BitArray x1_, BitArray x2_) {
      if (x1_ == null) {
          System.out.println("x1 is null");
          int b = x2_.getArray().length;
          byte[] array = new byte[b];
          System.arraycopy(x2_.getArray(), 0, array, 0, b);
          BitArray res = new BitArray(array);
          res.setSize(x2_.getSize());
          return res;
      } else if (x2_ == null) { 
          System.out.println("x2 is null");
          int b = x1_.getArray().length;
          byte[] array = new byte[b];
          System.arraycopy(x1_.getArray(), 0, array, 0, b);
          BitArray res = new BitArray(array);
          res.setSize(x1_.getSize());
          return res;
      }
  
      int size1 = x1_.getSize();
      int size2 = x2_.getSize();
      int size = (x1_.getSize() + x2_.getSize()) / 8 ;
      if ((size1 + size2)%8!=0) size++;
      byte[] result = new byte[size];
      System.arraycopy(x1, 0, result, 0, x1.length);
      BitArray res = new BitArray(result);
      res.setSize(size1 + size2);
      for (int i = 0 ; i&lt;size2 ; i++) {
          res.setBit(size1 + i, x2_.getBit(i) );
      }
      return res; 
  }
  </code></pre>