1. Introduction
Two’s complement is a fundamental concept in computer science, particularly when dealing with signed binary numbers. It enables the representation of both positive and negative integers within a fixed number of bits.
In this tutorial, we’ll calculate the 2’s complement of a number in Java.
2. What is Two’s Complement?
In computer systems, values are represented using a series of binary digits consisting of 0’s and 1’s. Different ways to encode the values in a binary representation exist, such as Signed magnitude, 1’s complement, 2’s complement, and so on.
Two’s complement notation is a very efficient way to store and perform operations on signed numbers. Here, the most significant bit (MSB) indicates the sign of the number, with 0 denoting a positive number and 1 a negative number. This representation streamlines addition and subtraction operations on binary numbers.
3. Algorithm
Let’s look at the algorithm for calculating 2’s complement of a number. The two’s complement value is identical to its binary representation for positive numbers. However, for a negative number, we can determine the two’s complement using the following algorithm:
if number >= 0
convert to binary and return
else
take the absolute value and convert to binary
calculate 1's complement by flipping 1s and 0s
Add 1 to the 1's complement and return the value
This algorithm calculates the 2’s complement value of the given number.
4. Implementation
We can implement the above algorithm in Java.
4.1. Algorithm Implementation
We’ll implement the logic step by step, as defined in the algorithm. We get the required number of bits for the representation from the user as input and the number itself. Moreover, we use BigInteger to represent the input number to support larger numbers.
Initially, we check whether the number is negative or not. We can convert the number to binary format if it’s non-negative and return the result. Otherwise, we proceed with the calculation of the two’s complement by invoking the respective method:
public static String decimalToTwosComplementBinary(BigInteger num, int numBits) {
if (!canRepresentInNBits(num, numBits)) {
throw new IllegalArgumentException(numBits + " bits is not enough to represent the number " + num
}
var isNegative = num.signum() == -1;
var absNum = num.abs();
// Convert the abs value of the number to its binary representation
String binary = absNum.toString(2);
// Pad the binary representation with zeros to make it numBits long
while (binary.length() < numBits) {
binary = "0" + binary;
}
// If the input number is negative, calculate two's complement
if (isNegative) {
binary = performTwosComplement(binary);
}
return formatInNibbles(binary);
}
We can use the toString() method with a radix value of 2 on the BigInteger to transform the number into its binary representation. Before converting, we take the absolute value of the input as the logic for 2’s complement is different for negative and positive numbers. Additionally, we append extra zeroes to the left of the binary value to ensure it aligns with the specified number of bits. Moreover, we verify if the number can be represented within the given number of bits:
private static boolean canRepresentInNBits(BigInteger number, int numBits) {
BigInteger minValue = BigInteger.ONE.shiftLeft(numBits - 1).negate(); // -2^(numBits-1)
BigInteger maxValue = BigInteger.ONE.shiftLeft(numBits - 1).subtract(BigInteger.ONE); // 2^(numBits-1) - 1
return number.compareTo(minValue) >= 0 && number.compareTo(maxValue) <= 0;
}
Now, let’s look at the implementation of the method performTwosComplement() that calculates the two’s complement for the negative number:
private static String performTwosComplement(String binary) {
StringBuilder result = new StringBuilder();
boolean carry = true;
// Perform one's complement
StringBuilder onesComplement = new StringBuilder();
for (int i = binary.length() - 1; i >= 0; i--) {
char bit = binary.charAt(i);
onesComplement.insert(0, bit == '0' ? '1' : '0');
}
// Addition by 1
for (int i = onesComplement.length() - 1; i >= 0; i--) {
char bit = onesComplement.charAt(i);
if (bit == '1' && carry) {
result.insert(0, '0');
} else if (bit == '0' && carry) {
result.insert(0, '1');
carry = false;
} else {
result.insert(0, bit);
}
}
if (carry) {
result.insert(0, '1');
}
return result.toString();
}
In this method, we initially calculate the 1’s complement of the given binary number by flipping the 1’s to 0’s and vice versa. Subsequently, we increment the resulting 1’s complement value by one, giving us the two’s complement value of the given binary string.
For better readability, we can implement a method to format the binary string in a group of nibbles(4 bits):
private static String formatInNibbles(String binary) {
StringBuilder formattedBin = new StringBuilder();
for (int i = 1; i <= binary.length(); i++) {
if (i % 4 == 0 && i != binary.length()) {
formattedBin.append(binary.charAt(i - 1)).append(" ");
} else {
formattedBin.append(binary.charAt(i - 1));
}
}
return formattedBin.toString();
}
The algorithm for computing the two’s complement is now fully implemented.
4.2. Alternative Implementation
Alternatively, based on the property of the binary addition, we can calculate the two’s complement more easily. In this method, we start iterating from the rightmost side of the binary string. Upon detecting the first 1, we invert all the bits on the left side of this bit. Let’s proceed with the implementation of this approach:
private static String performTwosComplementUsingShortCut(String binary) {
int firstOneIndexFromRight = binary.lastIndexOf('1');
if (firstOneIndexFromRight == -1) {
return binary;
}
String rightPart = binary.substring(firstOneIndexFromRight);
String leftPart = binary.substring(0, firstOneIndexFromRight);
String leftWithOnes = leftPart.chars().mapToObj(c -> c == '0' ? '1' : '0')
.map(String::valueOf).collect(Collectors.joining(""));
return leftWithOnes + rightPart;
}
This method provides a simpler approach to calculating the two’s complement of the given number.
5. Testing the Implementations
Now that the implementations are ready, let’s write the unit tests to check their accuracy. We can use the parameterized test from JUnit to cover multiple cases in a single test:
@ParameterizedTest(name = "Twos Complement of {0} with number of bits {1}")
@CsvSource({
"0, 4, 0000",
"1, 4, 0001",
"-1, 4, 1111",
"7, 4, 0111",
"-7, 4, 1001",
"12345, 16, 0011 0000 0011 1001",
"-12345, 16, 1100 1111 1100 0111"
})
public void givenNumberAndBits_getTwosComplement(String number, int noOfBits, String expected) {
String twosComplement = TwosComplement.decimalToTwosComplementBinary(new BigInteger(number), noOfBits);
Assertions.assertEquals(expected, twosComplement);
}
In this single test, we’ve included cases for various input numbers.
Similarly, we can also write the test for the second approach.
6. Conclusion
In this article, we discussed the calculation of two’s complement of a given number. In addition to the conventional algorithm, we introduced a simpler alternative for computation. Furthermore, we covered the implementations through parameterized tests to validate their accuracy.
As always, the sample code used in this article is available over on GitHub.
