为了找到一个数的二进制表示,我们需要寻找位
b0…bn,使得:
n = bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0
现在我们专注于寻找
b0, b1, ..., bn
。请注意,
(bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0) % 2 = b0
因为 b0 * 2^0 % 2 = b0
,而当 j >= 1
时,bj * 2^j % 2 = 0
,因为当 j >= 1
时,2^j % 2 = 0
。所以,
n = bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0
=> n % 2 = (bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0) % 2 = b0
我们发现
b0 = n % 2
。这是关键事实之一。
现在,让我们除以2:
n / 2 = (bn * 2^n + b_(n - 1) * 2^(n - 1) + ... + b1 * 2^1 + b0 * 2^0)
= bn * 2^(n - 1) + b_(n - 1) * 2^(n - 2) + ... + b1 * 2^1
现在,我们先停下来。仔细观察一下 n / 2
的二进制表示。注意到它与 n
的二进制表示完全相同,只是最后一位被去掉了。也就是说:
n = bn b_(n-1) ... b1 b0
n / 2 = b_n b_(n-1) ... b1
这是关键事实2.
因此,让我们总结一下我们所学到的内容。
n
的二进制表示是n/2
的二进制表示加上n
的二进制表示的最后一位数字。 这来自于关键事实2。
n
的二进制表示的最后一位数字可以通过计算n%2
来得到。 这来自于关键事实1。
所有这些都是正确的,除了一个情况:当n=0
时。在这种情况下,n
的二进制表示是0
。如果我们尝试使用除以2
的规则,我们将永远不会停止除以2。因此,我们需要一条规则来捕捉n=0
的情况。
因此,为了计算n
的二进制表示,首先计算n/2
的二进制表示,然后附加n%2
的结果,但一定要处理n=0
的情况。让我们把它写成代码:
void ToBin(int n) {
if(n > 1) {
ToBin(n / 2);
}
print(n % 2);
}