Skip to content

Commit 14c41ff

Browse files
dominiqueplantedominiqueplante
authored
Merge pull request #16488 from yadavan88/twos-complement
Added code to calculate twos complement of a number
2 parents a9717c3 + fb121ee commit 14c41ff

2 files changed

Lines changed: 165 additions & 0 deletions

File tree

‎core-java-modules/core-java-numbers-7/src/main/java/com/baeldung/twoscomplement/TwosComplement.java‎

Lines changed: 116 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,116 @@
1+
package com.baeldung.twoscomplement;
2+
3+
import java.math.BigInteger;
4+
import java.util.stream.Collectors;
5+
6+
public class TwosComplement {
7+
8+
public static String decimalToTwosComplementBinary(BigInteger num, int numBits) {
9+
if (!canRepresentInNBits(num, numBits)) {
10+
throw new IllegalArgumentException(numBits + " bits is not enough to represent the number " + num);
11+
}
12+
var isNegative = num.signum() == -1;
13+
var absNum = num.abs();
14+
15+
// Convert the abs value of the number to its binary representation
16+
String binary = absNum.toString(2);
17+
18+
// Pad the binary representation with zeros to make it numBits long
19+
while (binary.length() < numBits) {
20+
binary = "0" + binary;
21+
}
22+
23+
// If the input number is negative, calculate two's complement
24+
if (isNegative) {
25+
binary = performTwosComplement(binary);
26+
}
27+
28+
return formatInNibbles(binary);
29+
}
30+
31+
private static String performTwosComplement(String binary) {
32+
StringBuilder result = new StringBuilder();
33+
boolean carry = true;
34+
// Perform one's complement
35+
StringBuilder onesComplement = new StringBuilder();
36+
for (int i = binary.length() - 1; i >= 0; i--) {
37+
char bit = binary.charAt(i);
38+
onesComplement.insert(0, bit == '0' ? '1' : '0');
39+
}
40+
// Addition by 1
41+
for (int i = onesComplement.length() - 1; i >= 0; i--) {
42+
char bit = onesComplement.charAt(i);
43+
if (bit == '1' && carry) {
44+
result.insert(0, '0');
45+
} else if (bit == '0' && carry) {
46+
result.insert(0, '1');
47+
carry = false;
48+
} else {
49+
result.insert(0, bit);
50+
}
51+
}
52+
53+
if (carry) {
54+
result.insert(0, '1');
55+
}
56+
57+
return result.toString();
58+
}
59+
60+
private static String formatInNibbles(String binary) {
61+
StringBuilder formattedBin = new StringBuilder();
62+
for (int i = 1; i <= binary.length(); i++) {
63+
if (i % 4 == 0 && i != binary.length()) {
64+
formattedBin.append(binary.charAt(i - 1)).append(" ");
65+
} else {
66+
formattedBin.append(binary.charAt(i - 1));
67+
}
68+
}
69+
return formattedBin.toString();
70+
}
71+
72+
private static boolean canRepresentInNBits(BigInteger number, int numBits) {
73+
BigInteger minValue = BigInteger.ONE.shiftLeft(numBits - 1).negate(); // -2^(numBits-1)
74+
BigInteger maxValue = BigInteger.ONE.shiftLeft(numBits - 1).subtract(BigInteger.ONE); // 2^(numBits-1) - 1
75+
return number.compareTo(minValue) >= 0 && number.compareTo(maxValue) <= 0;
76+
}
77+
78+
public static String decimalToTwosComplementBinaryUsingShortCut(BigInteger num, int numBits) {
79+
if (!canRepresentInNBits(num, numBits)) {
80+
throw new IllegalArgumentException(numBits + " bits is not enough to represent the number " + num);
81+
}
82+
var isNegative = num.signum() == -1;
83+
var absNum = num.abs();
84+
85+
// Convert the abs value of the number to its binary representation
86+
String binary = absNum.toString(2);
87+
88+
// Pad the binary representation with zeros to make it numBits long
89+
while (binary.length() < numBits) {
90+
binary = "0" + binary;
91+
}
92+
93+
// If the input number is negative, calculate two's complement
94+
if (isNegative) {
95+
binary = performTwosComplementUsingShortCut(binary);
96+
}
97+
98+
return formatInNibbles(binary);
99+
}
100+
101+
private static String performTwosComplementUsingShortCut(String binary) {
102+
int firstOneIndexFromRight = binary.lastIndexOf('1');
103+
if (firstOneIndexFromRight == -1) {
104+
return binary;
105+
}
106+
String rightPart = binary.substring(firstOneIndexFromRight);
107+
String leftPart = binary.substring(0, firstOneIndexFromRight);
108+
String leftWithOnes = leftPart.chars().mapToObj(c -> c == '0' ? '1' : '0')
109+
.map(String::valueOf).collect(Collectors.joining(""));
110+
return leftWithOnes + rightPart;
111+
}
112+
113+
}
114+
115+
116+

‎core-java-modules/core-java-numbers-7/src/test/java/com/baeldung/twoscomplement/TwosComplementUnitTest.java‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package com.baeldung.twoscomplement;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
import org.junit.jupiter.api.Test;
5+
import org.junit.jupiter.params.ParameterizedTest;
6+
import org.junit.jupiter.params.provider.CsvSource;
7+
8+
import java.math.BigInteger;
9+
10+
public class TwosComplementUnitTest {
11+
12+
@ParameterizedTest(name = "Twos Complement of {0} with number of bits {1}")
13+
@CsvSource({
14+
"0, 4, 0000",
15+
"1, 4, 0001",
16+
"-1, 4, 1111",
17+
"7, 4, 0111",
18+
"-7, 4, 1001",
19+
"12345, 16, 0011 0000 0011 1001",
20+
"-12345, 16, 1100 1111 1100 0111"
21+
})
22+
public void givenNumberAndBits_getTwosComplement(String number, int noOfBits, String expected) {
23+
String twosComplement = TwosComplement.decimalToTwosComplementBinary(new BigInteger(number), noOfBits);
24+
Assertions.assertEquals(expected, twosComplement);
25+
}
26+
27+
@ParameterizedTest(name = "Twos Complement of {0} with number of bits {1}")
28+
@CsvSource({
29+
"0, 4, 0000",
30+
"1, 4, 0001",
31+
"-1, 4, 1111",
32+
"7, 4, 0111",
33+
"-7, 4, 1001",
34+
"12345, 16, 0011 0000 0011 1001",
35+
"-12345, 16, 1100 1111 1100 0111"
36+
})
37+
public void givenNumberAndBits_getTwosComplementUsingShortcut(String number, int noOfBits, String expected) {
38+
String twosComplement = TwosComplement.decimalToTwosComplementBinaryUsingShortCut(new BigInteger(number), noOfBits);
39+
Assertions.assertEquals(expected, twosComplement);
40+
}
41+
42+
@Test
43+
public void givenNumberOutsideBitsRange_throwException() {
44+
Exception ex = Assertions.assertThrows(IllegalArgumentException.class, () -> {
45+
TwosComplement.decimalToTwosComplementBinary(BigInteger.valueOf(8), 3);
46+
});
47+
Assertions.assertEquals("3 bits is not enough to represent the number 8", ex.getMessage());
48+
}
49+
}

0 commit comments

Comments
 (0)