Arithmetic Operations on Arbitrary-Length Binary Integers in Java

1. Overview

In digital signal processing, operations are often performed on the binary representations of signals. In computer graphics, bit manipulation is critical for color, pixel operations, and transformations. Cryptography makes extensive use of bit-level operations to perform encryption and hashing functions efficiently and securely. In all of these cases, working with binary numbers of arbitrary length is critical.

In this tutorial, we’ll look at the methods for performing arbitrary-precision arithmetic operations on binary numbers in Java, exploring both the use of the BigInteger class and alternative approaches for environments where BigInteger isn’t available or desired.

We’ll also look at the limitations of binary literals. This is important to clarify both why we can’t use Java’s primitive types and how negative binary numbers are represented.

2. Number of Bits of Binary Literals

We can use a binary literal to assign a binary integer written in two’s complement notation to a 32-bit Integer or to a 64-bit Long. It’s worth noting that Java APIs such as Integer.toBinaryString() and Long.toBinaryString() also use two’s complement notation.

Two’s complement notation means that positive numbers are written as they are in base 2, while negative numbers are written by adding 2³² if they are Integer or 2⁶⁴ if they are Long. This is exactly the same as taking the unsigned negative number written in 32bit or 64bit, inverting all the bits, and adding 1.

Let’s try a simple test:

@Test
void givenTwoBinaryLiterals_whenAdding_thenResultIsCorrect() {
    int a = 0b110100101101010;
    int b = 0b1000;
    int expected = 0b110100101110010; // Result of a + b in binary
    assertEquals(expected, a + b, "The addition of a and b should be correct");
}

Writing negative numbers is less intuitive because of the two’s complement notation. Let’s take the case of -8:

@Test
void whenComparingBinaryToDecimal_thenValuesAreEqual() {
    int c = 0b11111111111111111111111111111000; // (2^32 - 8) written in base 2
    int expected = -8;
    assertEquals(expected, c, "The binary value does not equal the decimal value of -8");
}

The main problem with binary literals is the maximum number of bits. Here is a screenshot from Eclipse:

So binary literals aren’t an option if we need to perform arbitrary-precision arithmetic operations. However, when we implement subtraction between binary numbers of arbitrary length, the two’s complement representation of negative numbers that we’ve just seen will come in handy again.

3. Arbitrary-Length Binary Integers

Binary integers of arbitrary length can be represented by String objects composed of 0s and 1s, or by BigInteger objects.

In general, BigInteger is the simplest, most complete, and least error-prone solution. When using BigInteger, we don’t have to use two’s complement notation. Instead, we can write numbers by specifying the sign (+ or –) followed by their absolute value. This is the usual way we represent numbers in everyday base-10 notation. If a number is positive, we can omit the + sign:

@Test
void givenTwoBigIntegers_whenAdding_thenResultIsCorrect() {
    BigInteger a = new BigInteger("1101001011010101010101010101010101010101010101010101010101010101010", 2);
    BigInteger b = new BigInteger("-10000", 2);
    BigInteger expected = new BigInteger("1101001011010101010101010101010101010101010101010101010101010011010", 2);
    assertEquals(expected, BigIntegerExample.add(a, b), "The addition of a and b should be correct");
}

However, there are special cases where BigInteger isn’t available. For example, Java ME CLDC 8 is used in machine-to-machine (M2M) and Internet of Things (IoT) devices, but it doesn’t include BigInteger. In these cases, implementing arbitrary-precision binary arithmetic from scratch helps us address specific scenarios and also has educational value. It allows us to deepen our understanding of low-level operations and the basics of binary arithmetic, which are often abstracted away by higher-level libraries.

Since the BinaryStringOperations class is mostly self-explanatory, we’ll only discuss the most relevant parts of the code.

3.1. Sign Representation and Testing

In our JUnit tests, the number a is 67 bits long to exceed the maximum length of 64 bits allowed by the long primitive type. The sign of the numbers in BinaryStringOperations is represented similarly to BigInteger:

@Test
void givenTwoBinaryStrings_whenAdding_thenResultIsCorrect() {
    String a = "1101001011010101010101010101010101010101010101010101010101010101010";
    String b = "-10000";
    String expected = "1101001011010101010101010101010101010101010101010101010101010011010"; // Expected result of a + b
    assertEquals(expected, BinaryStringOperations.add(a, b), "The addition of a and b should be correct");
}

As for the expected results of our tests, we calculated them with bc to make sure we didn’t make any mistakes:

$ bc -l
[...]
ibase=2
obase=2
1101001011010101010101010101010101010101010101010101010101010101010 + -10000
1101001011010101010101010101010101010101010101010101010101010011010

Our tests for the other operations have the same structure.

3.2. General Structure of the Four Operations

The add(), subtract(), multiply(), and divide() methods in the BinaryStringOperations class share these common structural properties:

• Validation → Some helper methods ensure that the inputs are valid binary strings
• Sign handling → We strip the sign with removePlusMinus(), determine the positivity of the numbers with isPositive(), and ensure that the correct sign is returned in the result
• Conditional logic based on sign → The methods contain conditional statements that handle different scenarios based on whether the input strings are positive or negative
• Helper methods → unsignedAdd(), unsignedSubtract(), unsignedMultiply(), and unsignedDivide() implement the core bit manipulation and calculation logic
  
• Edge case handling → We implemented special handling for edge cases, such as division by zero

Here we see how we applied these structural properties to the add() method:

static String add(String a, String b) {
    String unsignedA = removePlusMinus(a);
    String unsignedB = removePlusMinus(b);

    if (isPositive(a)) {
        if (isPositive(b)) {
            // Example: a=1011, b=1111
            return unsignedAdd(unsignedA, unsignedB);
        } else {
            // Example: a=1011, b=-1111
            return subtract(unsignedA, unsignedB);
        }
    } else {
        if (isPositive(b)) {
            // Example: a=-1011, b=1111
            return subtract(unsignedB, unsignedA);
        } else {
            // Example: a=-1011, b=-1111
            return '-' + unsignedAdd(unsignedA, unsignedB);
        }
    }
}

The subtract(), multiply(), and divide() methods follow a similar structure to ensure consistent handling of signed binary string operations.

3.3. unsignedAdd()

The unsignedAdd() method performs the addition of two unsigned binary strings. Its algorithm is similar to manual binary addition, done bit by bit from right to left, handling the carry bit as necessary.

The comments in the code make the various steps clear:

static String unsignedAdd(String a, String b) {
    validateUnsignedBinaryString(a);
    validateUnsignedBinaryString(b);
    
    // Remove leading zeros
    a = a.replaceFirst("^0+(?!$)", "");
    b = b.replaceFirst("^0+(?!$)", "");

    int length = Math.max(a.length(), b.length());

    // Pad the shorter string with leading zeros to make both strings of equal length
    a = String.format("%" + length + "s", a).replace(' ', '0');
    b = String.format("%" + length + "s", b).replace(' ', '0');

    StringBuilder result = new StringBuilder(length * 2);
    boolean carry = false;

    // Iterate from the LSB (least significant bit) to the MSB (most significant bit)
    for (int i = length - 1; i >= 0; i--) {
        // Determine the bit values of the current position for both strings
        boolean v1 = (a.charAt(i) == '1');
        boolean v2 = (b.charAt(i) == '1');

        // Calculate the result bit for the current position considering the carry
        boolean r = carry && v1 && v2 || carry && !v1 && !v2 || !carry && v1 && !v2 || !carry && !v1 && v2;

        // Update the carry for the next iteration
        carry = carry && v1 || carry && v2 || v1 && v2;

        // Insert the result bit at the beginning of the result string
        result.insert(0, r ? '1' : '0');
    }

    // If there is a carry left, insert it at the beginning of the result string
    if (carry) {
        result.insert(0, '1');
    }

    return result.toString();
}

The most difficult part of the code is the calculation of bits:

boolean r = carry && v1 && v2 || carry && !v1 && !v2 || !carry && v1 && !v2 || !carry && !v1 && v2;
[...]
carry = carry && v1 || carry && v2 || v1 && v2;

In a nutshell, we write the truth tables of the bit calculations on paper and copy them into simplogic.dev. Then it generates the boolean expressions that we insert into the code. We can achieve the same expressions manually by applying Karnaugh mapping and De Morgan’s theorems.

simplogic.dev also allows us to generate the truth tables we used from the code:

We use truth tables only for summation. The other methods don’t need them.

3.4. unsignedSubtract()

We do the subtraction using two’s complement, as we’ve already seen for binary literals. The simplest way is to invert the bits of b, add 1, and then add that value to a:

static String unsignedSubtract(String a, String b) {
    [...]

    // Two's complement step 1: invert all the bits
    StringBuilder inverted = new StringBuilder();
    for (int i = 0; i < b.length(); i++) {
        char c = b.charAt(i);
        if (c == '0') {
            inverted.append('1');
        } else {
            inverted.append('0');
        }
    }
    
    // Two's complement step 2: add 1 to the inverted bits
    String b2complement = addOne(inverted.toString());
    
    // Executes the sum between a and the two's complement of b
    // Since a>=b, the result will always have an extra bit due to the carry out
    // We remove this extra bit by using substring(1)
    String result = unsignedAdd(a, b2complement).substring(1);
    
    [...]
}

By subtracting in two’s complement, we can take advantage of the simpler and better understood process of binary addition, which involves only carrying, not borrowing. Thus, using two’s complement reduces the complexity and potential for error in the subtraction operation.

3.5. unsignedMultiply()

To perform the multiplication, we iterate over the bits of b, and for each bit that is set to 1, we add a shifted version of a to the result:

static String unsignedMultiply(String a, String b) {
    [...]
    
    // Iterate from the LSB (least significant bit) to the MSB (most significant bit) of "b"
    for (int i = b.length() - 1; i >= 0; i--) {
        zeros++;
        if (b.charAt(i) == '1') {
            // Calculate the partial product by appending the necessary number of zeros to "a"
            // and this partial product is added to the result
            result = unsignedAdd(result, appendZeros(a, zeros));
        }
    }
    
    return result;
}

In this way, we treat multiplication as a series of sums, just as we would in manual calculations. This reduces the complexity of the code.

3.6. unsignedDivide()

Again, our algorithm does the calculations as we would by hand. We iterate over the bits of the dividend, keeping track of the remainder, and build the result by comparing the remainder to the divisor at each step:

static String unsignedDivide(String a, String b) {
    [...]
    
    // Iterate through each bit of the dividend "a" from MSB to LSB
    for (int i = 0; i < a.length(); i++) {
        if (result.length() == 0) {
            // Initialize result and remainder if not yet done
            if (compareBinaryStrings(a.substring(0, i + 1), b) >= 0) {
                result.append('1');
                remainder = unsignedSubtract(a.substring(0, i + 1), b);
            }
        } else {
            // Concatenate the current bit of "a" to the remainder
            remainder += a.charAt(i);
            // Compare the current remainder with the divisor "b"
            if (compareBinaryStrings(remainder, b) >= 0) {
                // If remainder is greater than or equal to divisor, append '1' to result
                result.append('1');
                // Subtract divisor "b" from remainder
                remainder = unsignedSubtract(remainder, b);
            } else {
                // If remainder is less than divisor, append '0' to result
                result.append('0');
            }
        }
    }

    return result.toString();
}

In this code, we implement division using the previously implemented subtraction, which in turn uses addition.

3.7. Code Optimization?

Our BinaryStringOperations class provides correct algorithmic implementations for arbitrary-precision arithmetic. If we don’t have any special speed requirements, it’s fine.

However, the BigInteger class is significantly more optimized, with advanced and very complex algorithms that drastically reduce execution time compared to the basic methods we can implement from scratch.

4. Conclusion

In this article, we’ve explored different methods for performing arbitrary-precision arithmetic operations on binary numbers in Java. We discussed the limitations of binary literals and then looked at the use of the BigInteger class.

We also explored a custom implementation of arbitrary-precision binary arithmetic using the BinaryStringOperations class. This implementation is particularly useful in environments where BigInteger isn’t available, or when we want to delve into the algorithmic challenges of bit manipulation.