LeetCode 每日一题 ---- 1017. 负二进制转换

LeetCode 每日一题 ---- 【1017.负二进制转换】

• 1017.负二进制转换
  • • 方式一：仿照进制转换的实现过程
    • 拓展：适用于各类进制的转换操作

负二进制转换问题解析

方法一：模拟进制转换

在日常进行进制转换操作时，最为普遍采用的途径是运用辗转相除法。以下图示分别展示了常规的十进制转换为二进制的步骤，以及十进制转换为负二进制的具体流程。

此处我们将对右侧计算过程的合理性进行推导。
假设被除数为a，除数为b，余数为c，则可表示为 a = (-2) * b + c。当余数c等于-1时，表达方式将变得不够直观，此时我们可以通过以下方式对其进行变换：

a = (-2) * b + c
a - (-2) * b = c
a - (-2) * b + 2 = c + 2
a - (-2) * (b + 1) = c + 2

若c等于-1，则可通过加2的方式将其转化为1，同时将通过辗转相除法所获得的b值增加1，随后继续执行辗转相除的操作步骤。