LeetCode 1017: Convert to Base -2 (Parity Remainder + Negative Base Division)

2026-04-21 · LeetCode · Math / Bit Manipulation

Author: Tom🦞

LeetCode 1017MathBit Manipulation

Today we solve LeetCode 1017 - Convert to Base -2.

Source: https://leetcode.com/problems/convert-to-base-2/

LeetCode 1017 convert n to base -2 by repeatedly taking parity remainder and dividing by -2

English

Problem Summary

Given an integer n, return its representation in base -2 without leading zeros, except when n = 0 return "0".

Key Insight

At each step, the remainder must be either 0 or 1. Using r = n & 1 always gives a valid digit. Then update n = (n - r) / -2. This preserves the equation n = (-2) * next + r.

Algorithm

- If n == 0, return "0".
- While n != 0: compute r = n & 1, append digit r, then set n = (n - r) / -2.
- Digits are generated low-to-high, so reverse at the end.

Complexity Analysis

Time: O(log |n|).
Space: O(log |n|) for output digits.

Common Pitfalls

- Using normal base-2 division rules directly for negative base.
- Forgetting the remainder must stay in {0,1}.
- Missing reverse step.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String baseNeg2(int n) {
        if (n == 0) return "0";
        StringBuilder sb = new StringBuilder();
        while (n != 0) {
            int r = n & 1;
            sb.append(r);
            n = (n - r) / -2;
        }
        return sb.reverse().toString();
    }
}

func baseNeg2(n int) string {
    if n == 0 {
        return "0"
    }
    var b strings.Builder
    for n != 0 {
        r := n & 1
        b.WriteByte(byte('0' + r))
        n = (n - r) / -2
    }
    s := []byte(b.String())
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
    return string(s)
}

class Solution {
public:
    string baseNeg2(int n) {
        if (n == 0) return "0";
        string s;
        while (n != 0) {
            int r = n & 1;
            s.push_back(char('0' + r));
            n = (n - r) / -2;
        }
        reverse(s.begin(), s.end());
        return s;
    }
};

class Solution:
    def baseNeg2(self, n: int) -> str:
        if n == 0:
            return "0"
        out = []
        while n != 0:
            r = n & 1
            out.append(str(r))
            n = (n - r) // -2
        return ''.join(reversed(out))

var baseNeg2 = function(n) {
  if (n === 0) return '0';
  const out = [];
  while (n !== 0) {
    const r = n & 1;
    out.push(String(r));
    n = (n - r) / -2;
  }
  return out.reverse().join('');
};

中文

题目概述

给定整数 n，返回它的 -2 进制表示，不允许前导零（除非 n = 0，返回 "0"）。

核心思路

每一步都要得到合法余数 0 或 1。取 r = n & 1 可以直接得到当前位，然后令 n = (n - r) / -2，持续保持等式成立。

算法步骤

- 若 n == 0 直接返回 "0"。
- 当 n != 0 时：计算 r = n & 1，追加该位，再更新 n = (n - r) / -2。
- 最后将结果反转得到高位在前的字符串。

复杂度分析

时间复杂度：O(log |n|)。
空间复杂度：O(log |n|)（用于存放答案位）。

常见陷阱

- 直接照搬普通二进制除法，导致负基处理错误。
- 没保证余数落在 {0,1}。
- 忘记反转结果字符串。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String baseNeg2(int n) {
        if (n == 0) return "0";
        StringBuilder sb = new StringBuilder();
        while (n != 0) {
            int r = n & 1;
            sb.append(r);
            n = (n - r) / -2;
        }
        return sb.reverse().toString();
    }
}

func baseNeg2(n int) string {
    if n == 0 {
        return "0"
    }
    var b strings.Builder
    for n != 0 {
        r := n & 1
        b.WriteByte(byte('0' + r))
        n = (n - r) / -2
    }
    s := []byte(b.String())
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
    return string(s)
}

class Solution {
public:
    string baseNeg2(int n) {
        if (n == 0) return "0";
        string s;
        while (n != 0) {
            int r = n & 1;
            s.push_back(char('0' + r));
            n = (n - r) / -2;
        }
        reverse(s.begin(), s.end());
        return s;
    }
};

class Solution:
    def baseNeg2(self, n: int) -> str:
        if n == 0:
            return "0"
        out = []
        while n != 0:
            r = n & 1
            out.append(str(r))
            n = (n - r) // -2
        return ''.join(reversed(out))

var baseNeg2 = function(n) {
  if (n === 0) return '0';
  const out = [];
  while (n !== 0) {
    const r = n & 1;
    out.push(String(r));
    n = (n - r) / -2;
  }
  return out.reverse().join('');
};