【每日一题Day169】LC1107负二进制转换 | 模拟进位 位运算

负二进制转换【LC1107】

给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。

注意，除非字符串就是 "0"，否则返回的字符串中不能含有前导零。

18分钟 挺满足了

• 思路

  如果将二进制的幂变为-2，如果第$i$位为1，那么转化为十进制后的值为2i2^i2i，不难发现，偶数位的值不变，奇数位的值变为负数。我们要做的操作是使值不变，那么要加上奇数位的绝对值的两倍，也就是将奇数位相邻高位的值变为1。因此，我们从低位开始遍历该整数的二进制形式，使用变量记录进位结果，如果奇数位的值和进位的值对2取余为1，那么需要进位

• 实现

  class Solution {public String baseNeg2(int n) {if (n == 0) return "0";StringBuilder sb = new StringBuilder();int cnt = 0;while (n > 0 || cnt > 0){int num = n & 1;n = (n >> 1);int add = (num + cnt) % 2;            if (add == 1 && sb.length() % 2 == 1){cnt++;}sb.append(add); cnt = (num + cnt) / 2;}return sb.reverse().toString();}
  }
  

  • 复杂度

    • 时间复杂度：$O(logn)$

    • 空间复杂度：$O(1)$