Cracking Coding Interview - 5.2 Binary to String

Binary to String: Given a real number between 0 and 1 (e.g., 0.72) that is passed in as a double, print the binary representation. If the number cannot be represented accurately in binary with at most 32 characters, print “ERROR.'

Hints: #143, #167, #173, #269, #297

解法

这个题是看了答案才知道什么意思的。

给你一个数字0.72，让你求它的二进制，答案是是0.1001，实际上就是把后面的72算成二进制。

怎么算出来呢？这个问题可以这么理解，0.72的二进制有一堆01组成，但是我们不知道，我们得挨个找出来。可以这么做，看.小数点后面的第1个数字是0还是1、再看第2个数字、再看第3个数字。但是我们的二进制操作只支持整形不只支持小数点咋整？我们可以把这个数字* 2让它进到整形部分再判断：

1
2

num     = 0.1001000     (0.72)
num * 2 = 1.001000

结果是否>=1，如果是则该bit为1，否则为0。这里通过 * 2可以进位的原理和十进制通过* 10进位是一样的。比如0.72可以看成是7 * 10^-1 + 2 * 10^-2，而0.1001可以看成是 1 * 2^-1 + 0 * 2^-2 + 0 * 2^-3 + 1 * 2^-4 。通过 * 2可以将第一个小数位进入到整数，从而判断其是否为1。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public String binToStr(double num) {
  StringBuilder sb = new StringBuilder();
  sb.append('.');
  while (num > 0) {
    if (sb.length() > 32) {
      return "ERROR";
    }
    double r = num * 2;
    if (r >= 1) {
      sb.append('1');
      num = r - 1; // 减掉1，在下个迭代中处理剩余的小数
    } else {
      sb.append('0');
      num = r;
    }
  }
  return sb.toString();
}