实现有符号整数的二进制表示法。或者说,实现java.lang.Integer.toBinaryString()方法。
要想实现有符号整数的二进制表示法,我们首先需要知道有符号整数在计算机中是怎么存储的。
计算机中存储有符号整数,使用的是补码(two's complement)。正数的补码同原码(其二进制表示)相同。负数的补码是其绝对值的原码按位取反(反码,one's complement)后再加一。因此,在补码中只有一个0,也就是00000000000000000000000000000000
。而10000000000000000000000000000000
是最小的负数,在Java中也就是Integer.MIN_VALUE
。
同时,这也带来一个我们在实现toBinaryString()
函数时需要注意的问题,因为Java中Integer.MAX_VALUE
,也就是01111111111111111111111111111111
,的绝对值比Integer.MIN_VALUE
小1。所以如果我们先求Integer.MIN_VALUE
绝对值再求其二进制原码表示的话就会产生溢出。因此需要先将输入转化为Long
才能避免这个问题。
代码实现如下:
/**
* Implement java.lang.Integer.toBinaryString.
*/
public class ConvertBinary {
public ConvertBinary() {
super();
}
/**
* @param num The number to be converted to binary string
* @return String representation of the 2's complement of the number.
*/
public String toBinaryString(int num) {
Long new_num = Long.valueOf(num); // Case to Long to deal with Integer.MIN_VALUE
if (num == 0) {
return "0";
} else if (num > 0) {
// the 2's complement of a positive number is the binary representation
// of the number
return toBaseTwo(new_num, false);
} else { // num < 0
// the 2's complement of a negative number is the 1's complement of that number plus 1.
// the 1's complement of a negative number can be obtained by reverting all the digits
// of the base-two representation of it's absolute value.
new_num *= -1;
String result = toBaseTwo(new_num, true);
result = revertDigit(result);
result = addOne(result);
return result;
}
}
/**
* @param num The number to be converted to base 2 representation
* @param flag Boolean flag to indicates if 0s need to be complemented
* to make the base 2 representation 32 digits long. This is needed for negative original inputs.
* @return String representation of a base 2 representation.
*/
private String toBaseTwo(Long num, boolean flag) {
StringBuilder sb = new StringBuilder();
while (num > 0) {
long curr = num % 2;
num = num / 2;
sb.append(curr);
}
if (flag) {
while (sb.length() < 32) {
// add extra 0s to the binary string to make it 32 bits long
sb.append('0');
}
}
return sb.reverse().toString();
}
private String revertDigit(String num) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < num.length(); i++) {
sb.append(num.charAt(i) == '0' ? '1' : '0');
}
return sb.toString();
}
private String addOne(String num) {
StringBuilder sb = new StringBuilder();
int carryOver = 1;
int i = num.length() - 1;
for (; i >= 0; i--) {
int curr = num.charAt(i) - '0';
curr += carryOver;
if (curr == 2) {
carryOver = 1;
curr = 0;
} else {
carryOver = 0;
}
sb.append(curr);
}
return sb.reverse().toString();
}
}