企业官网建设流程全解析

LeetCode-Go 题解精读：1017. Convert to Base -2 —— 用 Go 短除法实现负二进制转换

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本文围绕 LeetCode 第 1017 题Convert to Base -2（十进制转负二进制）展开，完整讲解题目约束、负基数（base -2）与普通二进制的本质差异，并结合 LeetCode-Go 仓库中leetcode/1017.Convert-to-Base-2目录下的 Go 实现与测试用例，逐行剖析"短除法 + 余数修正"的通用套路。读完本文，你将掌握如何把任意十进制非负整数转换为负基数表示，并能独立迁移这套方法到其它负基数（如 base -3）问题中。

题目描述

给定一个十进制数N，返回一个由若干"0"和"1"组成的字符串，该字符串表示N在**负二进制（base -2）**下的值。

返回的字符串不允许含有前导零，除非字符串本身就是"0"。

三个官方示例：

示例 1： Input: 2 Output: "110" 解释: (-2)^2 + (-2)^1 = 4 - 2 = 2 示例 2： Input: 3 Output: "111" 解释: (-2)^2 + (-2)^1 + (-2)^0 = 4 - 2 + 1 = 3 示例 3： Input: 4 Output: "100" 解释: (-2)^2 = 4

约束条件：

• 0 <= N <= 10^9

题目大意

给出十进制数N，需要将其转换为负二进制（base -2）字符串。负二进制的每一位权重是(-2)^i，且允许的位取值只有0和1。除"0"本身外，输出不能带前导零。这是本项目 README.md 中数论分类下"Base conversion（进制转换）"算法的典型题目。

解题思路：负基数的短除法

常规"十进制转二进制"的思路是：不断用2去除目标数，记录每次的余数，最后把余数逆序拼接。本题是同一思路的变体——把除数从 2 换成 -2，即"短除法"。

但这里藏着一个关键陷阱：在负基数下，余数可能为负数。以N = 3为例，若直接模仿普通二进制：

3 / (-2) = -1 余 1 -1 / (-2) = 0 余 -1 ← 余数为负，非法

-1不能作为二进制位写入结果。因此需要在余数为负时做进位修正：给余数加 2，同时让商加 1。其数学依据是：

被除数 = 除数 × 商 + 余数 N = (-2) × q + r 当 r < 0 时，改写为： N = (-2) × (q + 1) + (r + 2)

因为r + 2 >= 0（r 最小为 -1 时得到 1），且r + 2 < 2，修正后的余数必然落在合法的{0, 1}区间内，从而保证每一位都是合法的0/1位。

以N = 3验证完整流程：

逆序拼接得到"111"，与示例 2 一致。

仓库源码实现解析

本仓库在 1017. Convert to Base -2.go 中给出了极简实现，完整代码如下：

package leetcode import "strconv" func baseNeg2(N int) string { if N == 0 { return "0" } res := "" for N != 0 { remainder := N % (-2) N = N / (-2) if remainder < 0 { remainder += 2 N++ } res = strconv.Itoa(remainder) + res } return res }

逐段拆解：

1. 零值特判：N == 0直接返回"0"，同时满足"无前导零"的约束——如果不提前返回，循环一次都不会执行，结果会是空字符串。
2. 循环终止条件：for N != 0，每次迭代取当前值对-2的余数作为一位，商作为下一轮被除数，直到商归零。
3. 负余数修正：if remainder < 0 { remainder += 2; N++ }正是前文推导的进位修正，保证每个输出位只可能是0或1。
4. 字符串拼接：strconv.Itoa(remainder) + res采用前插法（新位放在最前面），短除法先算出来的是低位，天然完成逆序，无需额外反转。

用N = 4验证一次完整的迭代过程（对应官方示例 3）：

最终输出"100"，与题目示例一致（(-2)^2 = 4）。

测试用例与验证

仓库配套的 1017. Convert to Base -2_test.go 以表格驱动的方式覆盖了题目给出的核心输入：

需要注意一个细节：该测试文件的para1017/ans1017结构承载了"参数-期望"的表格定义，但Test_Problem1017主体仅通过fmt.Printf打印【input】:... 【output】:...来人工核对结果，并未使用t.Errorf或if做自动断言。从源码事实看，baseNeg2(4)实际输出是"100"（即题目的正确答案），而测试数据表中写的是"110"；由于缺少断言逻辑，这不会导致测试失败，读者自行阅读时应以题目官方示例与函数实际输出为准。

如果你想在本地复现，进入对应目录后执行：

go test -v -run Test_Problem1017 .

若希望整仓验证，可参考仓库根目录的 gotest.sh，它对./leetcode/...全部包统一执行带覆盖率收集的测试：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

复杂度分析

• 时间复杂度：O(log₂N)。每轮迭代将N的绝对值近似减半，迭代次数与最终负二进制串长度同阶，即约log₂(N+1)位。
• 空间复杂度：O(log₂N)。需要存储与位数等长的结果字符串。

在题目约束0 <= N <= 10^9下，结果串最长约 30 位，int类型完全够用，不存在溢出风险（本项目 go.mod 声明为 Go 1.19 模块，代码遵循标准库strconv完成数字到字符串的转换）。

小结与延伸

负二进制转换的核心就一句话：沿用短除法，但每次除法后必须把负余数修正为非负的0/1。掌握这个"余数修正"模板后，你可以轻松扩展到任意负基数（如 base -3、base -4），只需相应调整除数与余数区间的上界。本仓库在 README.md 的 Number theory（数论）分类中把"Base conversion"列为专项算法，同一思想也可对照复习 1009. Complement of Base-10 Integer（按位取反）、1689. Partitioning Into Minimum Number Of Deci-Binary Numbers（十进制按位拆分）等进制类题目，形成体系化记忆。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go