Search code examples
javabit-manipulationsign-extension

What is the most efficient way in Java to sign extend an arbitrary length pattern of bits?

Let's say, for example, I have packed three 10 bit signed integers into a Java integer.

I can extract the 10 bits easily:

int unpacked = packed & 0x3FF;
packed >>= 10;
etc ...

But now I need to sign-extend the top bit (bit 9 from the right). Is there a quick way of doing this with resorting to testing the top bit and setting?

Perhaps there is a better way of unpacking that leaves the sign in place.

Solution

  • An alternative to shifting twice is flipping the sign and then subtracting it:

    int unpacked = packed & 0x3FF;
int extended = (unpacked ^ 0x200) - 0x200;

    If the sign was not set, flipping it sets it and subtracting it resets it again.

    If the sign was set, flipping it resets it, subtracting it sets it again but also borrows all the way to the top, setting all bits along the way.

    This has some advantages,

    • The code does not depend on the size of the target integer type, if unpacked and extended were long then the same thing would work.
    • XOR and subtraction can be a little cheaper, for example on Skylake you can do 4 of those basic operations per cycle but only 2 shifts. The latency is the same though, and it only matters if the available ILP in the code is high.
    • Shifts don't really algebraically combine, but XOR and subtraction can. For example if the next operation is to add some constant to extended, then that addition and the "subtract the sign" steps can be rolled into one operation.