24

I need to convert a Java BigInteger instance to its value in bytes. From the API, I get this method toByteArray(), that returns a byte[] containing the two's-complement representation of this BigInteger.

Since all my numbers are positive 128 bits (16 bytes) integer, I don't need the 2's-complement form that give me 128 bits + sign bit (129 bits)...

Is there a way to get the standard (without the 2's-complement form) representation directly from a BigInteger?

If not, how can I right shift the whole byte[17] array to lose the sign bit in order to get a byte[16] array?

7
  • In terms of shifting bits, I assume you've read up on the <<<, <<, >>, >>> operators in Java? Dec 10, 2010 at 10:29
  • 2
    @Martijn: Almost; there is no <<< operator in Java.
    – musiKk
    Dec 10, 2010 at 10:36
  • If the number is signed, the signed bit will be 0. Is there a reason you need to lose a leading 0? Why not just ignore it? Dec 10, 2010 at 10:37
  • 1
    @musiKk Right you are! Wishful thinking on my part ;p Dec 10, 2010 at 10:42
  • 128 bits is 6 bytes? Are you sure?
    – TonyK
    Dec 10, 2010 at 10:59

4 Answers 4

38

You don't have to shift at all. The sign bit is the most significant (= leftmost) bit of your byte array. Since you know your numbers will always be positive, it is guaranteed to be 0. However, the array as a whole is right-aligned.

So there are two cases: your left-most byte is 0x00 or not. If it is 0x00 you can safely drop it:

byte[] array = bigInteger.toByteArray();
if (array[0] == 0) {
    byte[] tmp = new byte[array.length - 1];
    System.arraycopy(array, 1, tmp, 0, tmp.length);
    array = tmp;
}

If it is not 0, then you cannot drop it - but your array will already be in the representation you want, so you don't have to do anything.

The above code should work for both cases.

9
  • 3
    SO user roman-nikitchenko pointed out that the entire body of the if can be simplified to a single line: array = Arrays.copyOfRange(array, 1, array.length);. With that variation, there's no need to declare a tmp array. That's a great hint, thanks for that! :-)
    – Thomas
    May 16, 2013 at 14:40
  • It's not declared, but it is still constructed, so it "only" leads to better readable code, no performance benefit. Readability is a certainly something you want to have though, hence the quotation marks. Note that you need more code if you want to create a statically sized array (as in the I2OSP function used for RSA etc.). Nov 29, 2014 at 12:00
  • @owlstead - Good comment. Another reason for using an existing library function rather than your own implementation is of course that the former has likely been widely tested. For a short piece of code like this one this may not be so relevant, and surely you still can screw up in how you call that library method. Readability should certainly be kept in mind as well, but it arguably lies in in the eye of the beholder: some may find the invocation of a well-named method more readable while others might prefer more explicitness, e.g., if they've never encountered the copyOfRange method before.
    – Thomas
    Nov 30, 2014 at 18:08
  • While i have seen this code in multiple projects which claims to return unsigned Byte array i would like to understand if the code above really returns the unsigned byte array. Lets assume that the left most byte is 0x00, when we remove it then, where is the guarantee that the next byte in the byte array i.e. the second from left to right is not negative i.e. that the sign bit in that byte is not set to "1". In this case if we try to construct a big integer from the new byte array we will get totally different number. Thus the question why it is safe to drop the leftmost byte if it is 0x00.
    – Tito
    Jan 26, 2015 at 8:33
  • @Tito: Please note the second paragraph in Kami's original question: "[...] all my numbers are positive [...]".
    – Thomas
    Jan 26, 2015 at 11:12
4

The first (most significant) byte in the byte array may not just contain the sign bit, but normal bits too.

E.g. this BigInteger:

new BigInteger("512")
    .add(new BigInteger("16"))
    .add(new BigInteger("1"));

has this bit pattern: 00000010 00010001

Which is to say the top byte (with the sign bit) also has 'normal' bits as you'd expect.

So, what do you want to get back?

00000010 00010001 (what you have) or
00000100 0010001? or
10000100 01??????
3

You could copy away the first byte. Or you could just ignore it.

BigInteger bi = BigInteger.ONE.shiftLeft(127);
byte[] bytes1 = bi.toByteArray();
System.out.println(Arrays.toString(bytes1));
byte[] bytes = new byte[bytes1.length-1];
System.arraycopy(bytes1, 1, bytes, 0, bytes.length);
System.out.println(Arrays.toString(bytes));
0

In case you want to meet the byte array representation of the popular GMP library, you will remove the leading zero as documented above and in addition flip the array to have the most significant byte at the end.

Your Answer

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

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