1. 引言
在计算机科学中，补码是处理有符号二进制数的基本概念。它使得在固定位数的表示下能够表示正负整数。
在这个教程中，我们将学习如何使用Java计算一个数的补码。
2. 什么是补码？
在计算机系统中，值通过一系列由0和1组成的二进制位来表示。不同的编码方式可以用于二进制表示，如原码、反码和补码等。
补码是一种高效存储和执行有符号数操作的方式。其中，最左边的位（MSB）指示数字的符号，0表示正数，1表示负数。这种表示方式简化了二进制数的加减运算。
3. 算法
让我们来看看计算补码的算法。对于正数，其补码值就等于其二进制表示。但对于负数，我们可以按照以下步骤来确定补码：
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
这个算法计算给定数字的补码值。
4. 实现
我们可以在Java中实现上述算法。
4.1. 算法实现
我们将逐步实现算法定义的逻辑。首先，从用户那里获取所需的位数表示和数字本身作为输入。此外，我们使用BigInteger类来表示输入数字，以支持更大的数值。
首先，检查数字是否为负数。如果是非负数，我们可以将其转换为二进制并返回结果。否则，我们将继续进行补码的计算：
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);
}
我们可以使用BigInteger的toString()方法，将基数设置为2，将数字转换为其二进制表示。转换前，取输入的绝对值，因为补码对正负数的逻辑不同。另外，我们会在二进制值的左边添加额外的零，以确保它与指定的位数对齐。同时，我们需要检查数字是否能在给定的位数内表示：
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;
}
现在，让我们看看计算负数补码的方法performTwosComplement()的实现：
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();
}
在这个方法中，我们首先计算给定二进制字符串的反码，即1变成0，0变成1。然后，我们将得到的反码加1，从而得到给定二进制字符串的补码值。
为了提高可读性，我们可以实现一个方法将二进制字符串分组为4位的字节：
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();
}
补码计算的算法现在已完全实现。
4.2. 替代实现
另一种更简单的计算方法基于二进制加法的性质。在这个方法中，我们从二进制字符串的最右边开始迭代。当检测到第一个1时，我们将这一位左边的所有位取反。现在让我们实现这个方法：
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;
}
这个方法提供了一种计算给定数字补码的简便方法。
5. 测试实现
现在实现好了，我们来编写单元测试以验证它们的准确性。我们可以使用JUnit的参数化测试来在一个测试中涵盖多个案例：
@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);
}
在这个单个测试中，我们包含了各种输入数字的案例。
同样，我们也可以为第二种方法编写测试。
6. 总结
在这篇文章中，我们讨论了如何计算给定数字的补码。除了常规算法，我们还引入了一种更简单的计算方法。此外，我们通过参数化测试覆盖了实现，以验证其准确性。
如往常一样，本文使用的示例代码可在GitHub上找到。