BigInteger to byte[]

Question

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?

Acetaldehyde

In terms of shifting bits, I assume you've read up on the <<<, <<, >>, >>> operators in Java? – Quaker

@Martijn: Almost; there is no <<< operator in Java. – Access

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? – Modulator

@Access Right you are! Wishful thinking on my part ;p – Quaker

128 bits is 6 bytes? Are you sure? – Brunette

@Peter Lawrey, I need to have 128bits integer not 129bits(including the leading 0), that's why I want to shift the array – Acetaldehyde

@Kami, you cannot have a 128-bit integer, you can only have a byte[], see my answer below. No shifting is required. The difference is just conceptual IMHO. – Modulator

Answer 1

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.

Pollie

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! :-) – Pollie

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.). – Dalrymple

@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. – Pollie

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. – Fattal

@Tito: Please note the second paragraph in Kami's original question: "[...] all my numbers are positive [...]". – Pollie

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? – Fattal

@Fattal I think you've got a fair point -- it really all depends on how you interpret the resulting sequence of 0's and 1's in the byte array. The way I read the question (especially paragraph #3: "without the 2's-complement form") the OP doesn't want the output to be interpreted as 2's complement but rather in ordinary binary representation. Therefore your concern is not an issue for her/him. And if your setup is different and you want the byte array to contain a valid 2's complement representation, there's no need to worry anyway: toByteArray will not return unnecessary leading 0x00-bytes. – Pollie

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. – Fattal

@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. – Pollie

Answer 2

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??????

Siloxane

Answer 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));

Modulator

Answer 4

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.

Debor