Chuyển đổi sang Base -2 trong C ++

Giả sử chúng ta có một số N, chúng ta phải tìm một chuỗi bao gồm "0" s và "1" s biểu thị giá trị của nó trong cơ số -2 (hai âm). Chuỗi trả về không được có số 0 đứng đầu, trừ khi chuỗi chính xác là "0". Vì vậy, nếu đầu vào là 2, thì đầu ra sẽ là “110”, là (-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 =2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=một chuỗi trống

• nếu N =0, thì trả về “0”

• trong khi N khác 0

  • rem:=N mod (- 2)

  • N:=N / (-2)

  • nếu rem <0 và rem:=rem + 2 và tăng N lên 1

  • ret:=ret + rem dưới dạng chuỗi

• đảo ngược chuỗi ret

• trả lại ret.

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

17

Đầu ra

10001