Decimal to Binary
给你一个非负整数 n。请返回它的二进制表示，形式为由 0 和 1 组成的字符串，且不带前导零。只有零本身的答案以 0 开头，写作 "0"。
函数
- ninteger
- 要转换的数字
- 返回值string
- 将 n 的二进制位表示为字符串
约束条件
0 ≤ n ≤ 231-1- 自己构建字符串，不要调用内置的进制转换功能。
示例
- 输入
- n = 13
- 输出
- "1101"
- 解释
13 = 8 + 4 + 1。8、4、2 和 1 对应的位置分别是1、1、0和1，读作1101。
- 输入
- n = 0
- 输出
- "0"
- 解释
- 零没有置位，但答案仍然需要一个数字，所以它是
"0"，而不是空字符串。
- 输入
- n = 64
- 输出
- "1000000"
- 解释
64等于2^6：64 位上是一个1，然后从 32 位到 1 位依次是六个0。
进阶
你能用同一个循环将 n 转换为 2 到 16 进制中的任意进制吗？对于大于 9 的数字，使用字母 a 到 f 表示，可以吗？
提示
逐个打开提示，每个都会多透露一点。
不需要知道其他二进制位，你能找出
n的哪一位？想一想奇数和偶数。最后一位数字是
n % 2。将n除以 2 并舍去余数，就会去掉这一位数字，并将下一位移到最后一位。重复执行：记录
n % 2，然后将n减半，直到n为 0。数字会从低位到高位依次得到，所以最后要将它们反转。0 需要单独处理。
题解
二进制数是若干个 2 的幂相加的结果，每一位数字表示某个 2 的幂是否参与了求和。你可以从最高位开始，通过减去 2 的幂来找出各位数字；也可以从最低位开始，通过反复除以 2 得到余数。除法是标准方法：它不需要先找到最大的 2 的幂，而且适用于任何进制。
从上方减去 2 的幂
思路
这是手动转换的方法。小于等于 n 的最大 2 的幂会得到第一位数字 1。然后每次将幂降低一级：如果这个幂小于等于剩余的数，就写下 1 并减去它；否则写下 0。
对于 13：8 可以放入（剩下 5），4 可以放入（剩下 1），2 不可以，1 可以。读出的数字是 1101。第一位始终是 1，所以不会出现前导零。只有当 power ≤ n / 2 时才将 power 加倍，这样可以找到不超过 n 的最大幂。一个 31 位的数字需要 31 步，即 O(log n)。
算法
- 如果
n是0，返回"0"。 - 将
power设为 1，并在power ≤ n / 2时将它加倍。 - 当
power > 0时：如果n ≥ power，追加1，并从n中减去power；否则追加0。 - 将
power减半并重复。 - 返回你追加的数字。
def toBinary(n):
if n == 0:
return "0"
# Largest power of two that is at most n. Comparing with n // 2 avoids overflow.
power = 1
while power <= n // 2:
power *= 2
bits = []
while power > 0:
if n >= power:
bits.append("1")
n -= power
else:
bits.append("0")
power //= 2
return "".join(bits)重复除以 2
思路
n % 2 是 n 的最后一位二进制数字。除以 2 并向下取整会去掉这一位，并将其余数字向右移动一位，这样下一位就会成为最后一位。重复这个过程，直到 n 为 0，这样就能依次收集到所有数字，从最低位开始。
对于 13，余数依次是 1、0、1、1（分别来自 13、6、3 和 1）；反过来读就是 1101。循环在 0 处停止，因此写出的最高位是 1。0 不会进入循环，所以需要单独检查。每一步都会将 n 减半：时间和空间复杂度均为 O(log n)。
算法
- 如果
n是0，返回"0"。 - 当
n > 0时，将n % 2作为一位数字追加，并将n设为向下取整后的n / 2。 - 反转这些数字，因为它们是从最低位开始得到的。
- 将它们作为字符串返回。
def toBinary(n):
if n == 0:
return "0"
bits = []
while n > 0:
# The remainder is the lowest bit that is left.
bits.append(str(n % 2))
n //= 2
# The bits came out lowest first, so turn them around.
bits.reverse()
return "".join(bits)
易错点和边界情况
- 为
0返回空字符串。数字为零时，除法循环不会运行，所以要先检查它。 - 忘记反转。余数从最低位开始出现，所以结果会是
011，而不是110。 - 在
/会返回小数的语言中使用它，例如 JavaScript、Lua 或 PHP。13 / 2必须变成6，所以要向下取整。 - 不断将幂翻倍，直到它大于
n。当n ≥ 2^30时，幂会达到2^31，这会导致 32 位整数溢出。 - 在 C 中，分配的空间太小：一个 31 位数字需要 31 个字符，外加结束符
'\0'。
常见问题3
如何将十进制数转换为二进制数？
不断将这个数除以 2，并记下每次的余数，直到这个数变成 0。按从最后一个到第一个的顺序读取余数。对于 13，余数依次为 1、0、1、1，所以 13 的二进制表示是 1101。
将十进制转换为二进制的时间复杂度是多少？
每一步都会将数字减半，所以循环会按二进制位数运行，大约运行 log2(n) 次。这需要 O(log n) 的时间，答案字符串需要 O(log n) 的空间。对于 32 位整数，最多需要 31 步。
你能用位运算代替除法来转换为二进制吗？
是的。n & 1 会得到最低位，n >> 1 会将它去掉，对于非负数，这与 n % 2 和 n / 2 的效果相同。循环和反转过程保持不变。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def toBinary(n):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
n = 13
预期输出
"1101"