7

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?

4 Answers 4

18

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
7
  • Can this be done using type long in this case 2 longs?
    – k.ken
    Mar 14, 2015 at 1:55
  • Confused. Your input is 2 longs and your output is 2 longs bit shifted right?
    – Adam
    Mar 14, 2015 at 8:05
  • Wow, using two longs is a lot messier than I expected. The reason I was curious about using Longs is that BigInteger's toByteArray doesn't give me a 16byte array. I'd have to pad it. From your long example, it is not circular rotation right?
    – k.ken
    Mar 14, 2015 at 11:21
  • 1
    @k.ken I've rewritten answer to use shifting rather than rotating which simplifies things a little, I've also updated with problem about not padding output.
    – Adam
    Mar 14, 2015 at 12:53
  • What happened to the 7s? The final output should have the 7s, no? The long shift does not seem circular. Should the 7777 wrap to the front?
    – k.ken
    Mar 14, 2015 at 13:31
4

1. Manually implemented

Here are left and right shift implementation without using BigInteger (i.e. 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.

1
3

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;
}
0
0

The is an old post, but I want to update Adam's answer. The long solution works with a few tweak.

In order to rotate, use >>> instead of >>, because >> will pad with significant bit, changing the original value.

second, the printbyte function seems to miss leading 00 when it prints. use this instead.

private String getHexString(byte[] b) {
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < b.length; i++)
        result.append(Integer.toString((b[i] & 0xff) + 0x100, 16)
                .substring(1));
    return result.toString();
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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