25

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?

Improve this question
7
  • In terms of shifting bits, I assume you've read up on the <<<, <<, >>, >>> operators in Java? Commented Dec 10, 2010 at 10:29
  • 2
    @Martijn: Almost; there is no <<< operator in Java. Commented 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? Commented Dec 10, 2010 at 10:37
  • 1
    @musiKk Right you are! Wishful thinking on my part ;p Commented Dec 10, 2010 at 10:42
  • 128 bits is 6 bytes? Are you sure? Commented Dec 10, 2010 at 10:59

5 Answers 5

Reset to default
37

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

12 Comments

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! :-)
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.).
Thomas maybe i am missing something but i have read that again, and still the question is even if the all numbers are positive , it could happen that the first byte is 0x00 why it should be save to drop it, if after i try and create a big integer from the new byte array i.e. without the 0x00 byte then this is totally different big integer, or what I am missing here?
well my test shows that BigInteger.toByteArray() does return the leading zero byte. and if you drop that byte and then make an instance of BigInteger after you have droped it then that is a totally different bigInteger then the first one. As far as i understand there is no way in java where you can get a 1;s complement of BigInteger. it is always a 2's complement according to the java doc of the big Integer.
@Tito: Please note that I wrote "...will not return unnecessary leading 0x00-bytes", that is, if you do want your byte array to be interpreted as 2's complement then toByteArray already does the right thing and hence there's no need to worry about dropping bytes. toByteArray returns the shortest byte sequence that still correctly represents the number.
|
5

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??????
Improve this answer

Comments

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));
Improve this answer

Comments

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.

Improve this answer

Comments

0

If you know that your BigInteger represents an unsigned 128-bit (16-byte) number, you can use the following code to modify the result of BigInteger.toByteArray:

byte[] bytes = bigInteger.toByteArray(); if (bytes.length > 16) { // length not what we expected: remove the extra leading 0 sign byte // (i.e. return the last 16 bytes of array) int nExtraBytes = bytes.length - 16; return Arrays.copyOfRange(bytes, nExtraBytes, bytes.length); } else if (bytes.length < 16) { // original array passed to the BigInteger(int signum, byte[] magnitude) // constructor must've had multiple leading 0 bytes which were ignored, // so prepend those leading 0 bytes int nMissingBytes = 16 - bytes.length; byte[] padded = new byte[16]; System.arraycopy(bytes, 0, padded, nMissingBytes, bytes.length); return padded; } return bytes;

This requires prior knowledge of the number of bytes you expect (i.e. 16 if you have a 128-bit number).

Note: this code is a modification of the original accepted answer, to correctly handle a case where the leading 0 byte must not be removed (see my comment for an example), and to also ensure that you get an array of exactly 16 bytes (which preserves all the leading 0 bits of a 128-bit number).

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.