# [JAVA] Bitwise operation of binary value with BigInteger

Since Java does not have many convenient functions for handling binary values, in order to perform bit operations on a byte array in which binary values are stored, the value passing process between bits (array) is implemented by itself. need to do it.

A commonly used method is to store the byte array in an integer type such as int type or long type once, perform bit operations, and then return it to the byte array again. With this method, the maximum length is 8 bytes. Can only handle up to.

By using BigInteger class, you can handle byte array of any size, but data conversion I need to devise a little, so I summarized the points.

#### How to perform bit operation of byte array with BigInteger

Bit operation of byte array using BigInteger can be done by the following procedure.

1. Read the byte array as a positive number into BigInteger.
• [BigInteger (byte [] val)](https://docs.oracle.com/javase/jp/8/docs/api/java/math/BigInteger.html#BigInteger-byte: A-) Read by the constructor Later, the sign bit is changed to 0 by masking.
1. Perform various operations using the methods of the BigInteger instance.
• Increment decrement: add method, subtract method
• Logical operation: and method, or methods etc.
• Shift operation: shiftRight method, [shiftLeft](https: / /docs.oracle.com/javase/jp/8/docs/api/java/math/BigInteger.html#shiftLeft-int-) method
• These are arithmetic shifts, but the results are the same as logical shifts. (See point 1)
• Mask processing is performed after each operation to make the BigInteger value positive and convert each bit of unnecessary high-order bytes to 0.
1. Convert BigInteger to byte array again.
• Convert to byte array with toByteArray method and the number of bytes is insufficient. If there are many bytes, perform completion processing, and if there are many bytes, perform reduction processing.

#### Implementation example

• ideone.com (Check operation online)
• https://ideone.com/VC1LsH
• GitHub (source code)
• https://github.com/unhurried/bitwise-operation-with-biginteger

#### Point 1: Keep BigInteger always positive

If the value of BigInteger becomes negative, it may not work.

##### Arithmetic shift substitution for logical shift

Only arithmetic shift is implemented in BigInteger. (Because BigInteger is a class for handling numerical values without being aware of byte strings, logical shift has no meaning.) Therefore, it is necessary to substitute logical shift with logical shift, but right shift for negative numbers is The results differ between arithmetic shift and logical shift.

``````1010 1010 --1bit logical right shift--> 0101 0101
1010 1010 --1bit arithmetic right shift--> 1101 0101 #The result is different from the logical shift.
``````

Therefore, it is necessary to convert the value of BigInteger so that it is always a positive number. This conversion process needs to be performed after the first byte array read and each operation.

``````1010 1010
--Convert to BigInteger as a positive number--> 0000 1010 1010
--1bit arithmetic right shift--> 0000 0101 0101 #The result is the same as a logical shift.
``````

There are two ways to make BigInteger a positive number, one is to specify the sign bit and read the byte array, and the other is to change the sign bit to 1 by mask processing. Mask processing that can also be used for the purpose of point 2 described later It's easy to do.

``````//Input byte array: c0 00
byte[] input = new Bytes(new byte[] {(byte) 0xc0, (byte) 0x00}).toByteArray();

//How to read as a positive number (sign bit is 0)
// 00 c0 00
new BigInteger(1, input).toByteArray();

//How to change the sign bit to 0 by masking
// ff c0 00 (input) AND 00 ff ff (mask) => 00 c0 00
//* In the AND operation of BigInteger, which has a different size when it is converted to a byte array,
//The smaller one is expanded to fit the larger one.
BigInteger mask = new BigInteger(1, new Bytes(new byte[] {(byte) 0xff, (byte) 0xff}).toByteArray());
``````

#### Point 2: Keep each bit of the extra high-order byte at 0

When increment / decrement is performed on a BigInteger instance and the range that can be expressed by the original number of bytes is exceeded, or when a left shift operation is performed, the data is displayed in bytes higher than the original number of bytes. It may remain.

Since this extra high-order byte data affects the shift operation in the subsequent processing, it is necessary to clear each bit to 0 after each operation. This can be done at the same time with the masking process described in point 1.

``````//Input byte array: c0 00
byte[] input = new Bytes(new byte[] {(byte) 0xc0, (byte) 0x00}).toByteArray();
BigInteger mask = new BigInteger(1, new Bytes(new byte[] {(byte) 0xff, (byte) 0xff}).toByteArray());
//Shift calculation is performed in the order of 1-bit left shift and 1-bit right shift.
//Originally, the most significant 1 bit is discarded and it becomes 80 00, but it returns to the original c 0 00.
``````

#### Point 3: Adjust the number of bytes when returning BigInteger to the byte array

toByteArray method is required to represent the numbers stored in BigInteger. Since the byte array with the minimum number of elements is returned, the byte array may be smaller in size than the original byte array.

``````//Input byte array: 00 7f
byte[] input = new Bytes(new byte[] {(byte) 0x00, (byte) 0x7f}).toByteArray();
//Output byte array: 7f
//Converted to BigInteger, it becomes 1 byte. (Because 127 can be expressed in 1 byte as a number.)
byte[] output = new BigInteger(input).toByteArray();
``````

In addition, each operation may result in a byte array having a size larger than the original byte array.

``````//Input byte array: 40 00
byte[] input = new Bytes(new byte[] {(byte) 0x40, (byte) 0x00}).toByteArray();
//Output byte array after 1-bit left arithmetic shift: 00 80 00
byte[] output = new BigInteger(input).shiftLeft(2).toByteArray();
``````

Therefore, when returning to the byte array, it is necessary to adjust so that it matches the original number of bytes.

``````//BigInteger instance to be converted
BigInteger bi;
//The size of the byte array to convert
int byteSize;

byte[] ba = bi.toByteArray();
ByteBuffer bb = ByteBuffer.allocate(byteSize);
//Remove the extra high-order bytes.
if (ba.length >= byteSize) {
bb.put(ba, ba.length-byteSize, byteSize);
//Fill the ByteBuffer from the beginning for the number of missing bytes.
} else {
int byteSizeToFill = byteSize - ba.length;
for(int i=0; i<byteSizeToFill; i++) {
bb.put((byte) 0);
}
bb.put(ba);
}

//Byte array after conversion
byte[] output = bb.array();
``````

Strictly speaking, if BigInteger is a negative number, it is necessary to fill the missing bytes with 1 instead of 0, but since the value of BigInteger is adjusted so that it is always a positive number in correspondence with point 1, the case of a negative number No need to consider.

``````//Input byte array: ff ff
byte[] input = new Bytes(new byte[] {(byte) 0xff, (byte) 0xff}).toByteArray();
//Output byte array: ff
//In the case of a negative number, it is necessary to fill the missing high-order bits with 1.
byte[] output = new BigInteger(input).toByteArray();
``````

Recommended Posts