Bit shift operations on a byte array in Java

Question

How do I shift a byte array n positions to the right? For instance shifting a 16 byte array right 29 positions? I read somewhere it can be done using a long? Would using a long work like this:

Long k1 = byte array from 0 to 7

Long k2 = byte array from 8 to 15

Then right rotating these two longs using Long.rotateRight(Long x, number of rotations).How would the two longs be joined back into a byte array?

Solution 1

I believe you can do this using java.math.BigInteger which supports shifts on arbitrarily large numbers. This has advantage of simplicity, but disadvantage of not padding into original byte array size, i.e. input could be 16 bytes but output might only be 10 etc, requiring additional logic.

BigInteger approach

byte [] array = new byte[]{0x7F,0x11,0x22,0x33,0x44,0x55,0x66,0x77};

// create from array
BigInteger bigInt = new BigInteger(array);

// shift
BigInteger shiftInt = bigInt.shiftRight(4);

// back to array
byte [] shifted = shiftInt.toByteArray();

// print it as hex
for (byte b : shifted) {
    System.out.print(String.format("%x", b));
}

Output

7f1122334455667   <== shifted 4 to the right. Looks OK

Long manipulation

I don't know why you'd want to do this as rotateRight() as this makes life more difficult, you have to blank at the bits that appear at the left hand side in K1 etc. You'd be better with using shift IMO as describe below. I've used a shift of 20 as divisible by 4 so easier to see the nibbles move in the output.

1) Use ByteBuffer to form two longs from 16 byte array

byte[] array = { 0x00, 0x00, 0x11, 0x11, 0x22, 0x22, 0x33, 0x33, 0x44, 0x44, 0x55, 0x55, 0x66, 0x66, 0x77, 0x77 };
ByteBuffer buffer = ByteBuffer.wrap(array);
long k1 = buffer.getLong();
long k2 = buffer.getLong();

2) Shift each long n bits to the right

int n = 20;

long k1Shift = k1 >> n;
long k2Shift = k2 >> n;

System.out.println(String.format("%016x => %016x", k1, k1Shift));
System.out.println(String.format("%016x => %016x", k2, k2Shift));

0000111122223333 => 0000000001111222
4444555566667777 => 0000044445555666

Determine bits from k1 that "got pushed off the edge"

long k1CarryBits = (k1 << (64 - n));
System.out.println(String.format("%016x => %016x", k1, k1CarryBits));

0000111122223333 => 2333300000000000

Join the K1 carry bits onto K2 on right hand side

long k2WithCarray = k2Shift | k1CarryBits;
System.out.println(String.format("%016x => %016x", k2Shift, k2WithCarray));

0000044445555666 => 2333344445555666

Write the two longs back into a ByteBuffer and extract as a byte array

buffer.position(0);
buffer.putLong(k1Shift);
buffer.putLong(k2WithCarray);
for (byte each : buffer.array()) {
    System.out.print(Long.toHexString(each));
}

000011112222333344445555666

Solution 2

Here is what I came up with to shift a byte array by some arbitrary number of bits left:

/**
 * Shifts input byte array len bits left.This method will alter the input byte array.
 */
public static byte[] shiftLeft(byte[] data, int len) {
    int word_size = (len / 8) + 1;
    int shift = len % 8;
    byte carry_mask = (byte) ((1 << shift) - 1);
    int offset = word_size - 1;
    for (int i = 0; i < data.length; i++) {
        int src_index = i+offset;
        if (src_index >= data.length) {
            data[i] = 0;
        } else {
            byte src = data[src_index];
            byte dst = (byte) (src << shift);
            if (src_index+1 < data.length) {
                dst |= data[src_index+1] >>> (8-shift) & carry_mask;
            }
            data[i] = dst;
        }
    }
    return data;
}

Solution 3

1. Manually implemented

Here are left and right shift implementation without using BigInteger (ie. without creating a copy of the input array) and with unsigned right shift (BigInteger only supports arithmetic shifts of course)

Left Shift <<

/**
 * Left shift of whole byte array by shiftBitCount bits. 
 * This method will alter the input byte array.
 */
static byte[] shiftLeft(byte[] byteArray, int shiftBitCount) {
    final int shiftMod = shiftBitCount % 8;
    final byte carryMask = (byte) ((1 << shiftMod) - 1);
    final int offsetBytes = (shiftBitCount / 8);

    int sourceIndex;
    for (int i = 0; i < byteArray.length; i++) {
        sourceIndex = i + offsetBytes;
        if (sourceIndex >= byteArray.length) {
            byteArray[i] = 0;
        } else {
            byte src = byteArray[sourceIndex];
            byte dst = (byte) (src << shiftMod);
            if (sourceIndex + 1 < byteArray.length) {
                dst |= byteArray[sourceIndex + 1] >>> (8 - shiftMod) & carryMask;
            }
            byteArray[i] = dst;
        }
    }
    return byteArray;
}

Unsigned Right Shift >>>

/**
 * Unsigned/logical right shift of whole byte array by shiftBitCount bits. 
 * This method will alter the input byte array.
 */
static byte[] shiftRight(byte[] byteArray, int shiftBitCount) {
    final int shiftMod = shiftBitCount % 8;
    final byte carryMask = (byte) (0xFF << (8 - shiftMod));
    final int offsetBytes = (shiftBitCount / 8);

    int sourceIndex;
    for (int i = byteArray.length - 1; i >= 0; i--) {
        sourceIndex = i - offsetBytes;
        if (sourceIndex < 0) {
            byteArray[i] = 0;
        } else {
            byte src = byteArray[sourceIndex];
            byte dst = (byte) ((0xff & src) >>> shiftMod);
            if (sourceIndex - 1 >= 0) {
                dst |= byteArray[sourceIndex - 1] << (8 - shiftMod) & carryMask;
            }
            byteArray[i] = dst;
        }
    }
    return byteArray;
}

Used in this class by this Project.

2. Using BigInteger

Be aware that BigInteger internally converts the byte array into an int[] array so this may not be the most optimized solution:

Arithmetic Left Shift <<:

byte[] result = new BigInteger(byteArray).shiftLeft(3).toByteArray();

Arithmetic Right Shift >>:

byte[] result = new BigInteger(byteArray).shiftRight(2).toByteArray();

3. External Library

Using the Bytes java library*:

Add to pom.xml:

<dependency>
    <groupId>at.favre.lib</groupId>
    <artifactId>bytes</artifactId>
    <version>{latest-version}</version>
</dependency>

Code example:

Bytes b = Bytes.wrap(someByteArray);
b.leftShift(3);
b.rightShift(3);
byte[] result = b.array();

_{*Full Disclaimer: I am the developer.}