C++で整数を負の2進数（Base -2）に変換する方法

問題の概要

ある整数 N が与えられたとき、「0」と「1」だけから構成される文字列で、その値を負の2進数（基数 -2）で表現することを考えます。ただし、返す文字列の先頭に余分なゼロを付けてはいけません。例外として、値がちょうど 0 の場合は「0」を返します。

例えば、入力が 2 の場合、出力は「110」になります。これは次のように計算できます。

1 × (-2)^2 + 1 × (-2)^1 + 0 × (-2)^0 = 4 − 2 + 0 = 2

解法のアプローチ

通常の2進数変換と似ていますが、基数が負であるため、剰余が負になった場合の処理がポイントになります。以下の手順で解きます。

• 結果を格納する空の文字列 ret を用意します。

• N が 0 なら「0」を返します。

• N が 0 になるまで次を繰り返します。

  • rem := N mod (-2)（剰余を計算）

  • N := N / (-2)（商を計算）

  • rem が負の場合は rem に 2 を加え、N に 1 を足して補正します。

  • rem を文字列として ret に連結します。

• 最後に ret を反転させて返します。

剰余の補正が必要な理由は、C++ の除算では剰余が負になることがあるためです。桁として使えるのは 0 か 1 だけなので、rem が負になったら 2 を加えて非負にし、その分を商（上位の桁）に繰り上げます。これにより、すべての整数を符号なしで一意に表現できるようになります。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string baseNeg2(int N) {
        string ret = "";
        if(N == 0) return "0";
        while(N){
            int rem = N % (-2);
            N /= -2;
            if(rem < 0) rem += 2, N++;
            ret += to_string(rem);
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.baseNeg2(17));
}

入力

17

出力

10001

出力「10001」は、1 × (-2)⁴ + 0 + 0 + 0 + 1 × (-2)⁰ = 16 + 1 = 17 となり、正しく 17 を表していることが確認できます。

まとめ

負の基数への変換は、通常の基数変換と同じく「商と剰余を繰り返し求める」ことで実現できます。負の基数特有の注意点は、剰余が負になった場合に「剰余に基数の絶対値を加算し、商を 1 増やす」という補正を行うことです。この手法を使えば、任意の整数を記号「−」を使わずに 0 と 1 のみで表現できます。