解题思路

十进制转二进制有一个经典方法，叫除 2 取余法：

把一个十进制数不停地除以 2，把每次除得的余数（不是 0 就是 1）记下来，直到这个数变成 0。最后把所有余数倒过来写，就得到它的二进制表示。

举个例子，把 89 转成二进制：

• 89 ÷ 2 = 44 余 1
• 44 ÷ 2 = 22 余 0
• 22 ÷ 2 = 11 余 0
• 11 ÷ 2 = 5 余 1
• 5 ÷ 2 = 2 余 1
• 2 ÷ 2 = 1 余 0
• 1 ÷ 2 = 0 余 1

把余数从下往上倒过来读：1011001，这就是 89 的二进制。

在程序里，我们用数组把余数一个一个存下来，存完后倒序输出。要注意特殊情况：如果输入的是 0，它的二进制就是 0，直接输出 0。

参考代码

// P4515 十进制转二进制：用除2取余法转换
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 0) {
        cout << 0 << endl; // 0 的二进制就是 0
        return 0;
    }
    int a[100], len = 0;
    while (n > 0) {
        a[len++] = n % 2; // 记录除以2的余数（二进制的一位）
        n /= 2;
    }
    for (int i = len - 1; i >= 0; i--) // 余数要倒序输出
        cout << a[i];
    cout << endl;
    return 0;
}

复杂度分析

每除一次 2，数值就缩小一半，所以一共要除大约 log₂(n) 次，也就是二进制有多少位就循环多少次，时间复杂度是 O(log n)。用一个数组存二进制位，空间复杂度也是 O(log n)。