【题解】奇怪的电脑 位运算

老师叫我去给小朋友们讲他们的考试题，一共四道，前三题都傻逼题

第四题。。。我卡壳了

题面：

样例输入：

-13

样例输出：

110111

嗯，怎么做呢

其实题目就是要你找一个二进制上 $1, 3, 5, 7, …$位为 $0$的数字 $A$，以及一个二进制上 $0, 2, 4, 6, …$位为 $0$的数字 $B$，使得 $A – B$等于输入的 $n$

因为是 $-2$进制因此可以从 $2$进制角度考虑

对于 $n$的二进制在 $0, 2, 4, …$位上的 $1$，只要让 $A$的对应位 $+1$即可

对于 $n$在 $1, 3, 5, …$位上的 $1$，我们无法让 $A$直接增加，而是应该 “曲线救国”，让 $B$的这一位 $+1$，再让 $A$的下一位 $+1$，这样两者相减就能得到这一位了

现在的问题就是怎么 $+1$

拿 $A$举例，如果 $A$的这一位为 $0$，那直接把这一位设为 $1$即可

如果 $A$这一位为 $1$，有两种：

• 如果 $B$的下一位为 $1$，那直接把 $A$的当前位设为 $0$，然后让 $B$的下一位也置为 $0$，这样相当于二进制下给 $A$进一位
• 否则把 $B$的下一位置为 $1$，把 $A$的 “下一个位置的下一个位置” 置为 $1$，然后把 $A$的当前位置为 $0$，也相当于进了一位

$B$的同理

然后这个进位过程用递归处理即可

对于负数，可以先找到最小的一个 $\geq n$的 $2 ^ k$（$k$为正整数），使得 $n + 2 ^ k \geq 0$，然后算出 $n + 2 ^ k$这个非负整数的答案，最后再给 $B$的第 $k$位 $+1$即可（减掉 $2 ^ k$）

多妙啊～

（其实我不确定我这个做法是否是最优的）

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

LL n, m;

bool A[70], B[70];

void markA(int), markB(int);

void markA(int a)
{
    if (!A[a]) A[a] = 1;
    else
    {
        if (B[a + 1]) B[a + 1] = 0;
        else markA(a + 2), markB(a + 1);
        A[a] = 0;
    }
}

void markB(int a)
{
    if (!B[a]) B[a] = 1;
    else
    {
        if (A[a + 1]) A[a + 1] = 0;
        else markB(a + 2), markA(a + 1);
        B[a] = 0;
    }
}

int main(int argc, char const* argv[])
{
    IN(n);
    if (n < 0)
    {
        m = 1;
        while (m + n < 0) m <<= 1;
        n += m;
    }
    int x = 0;
    while (n)
    {
        if (n & 1)
        {
            if (x & 1) markA(x + 1), markB(x);
            else markA(x);
        }
        n >>= 1, x++;
    }
    if (m)
    {
        x = 0;
        while ((1ll << x) < m) x++;
        if (x & 1) markB(x);
        else markB(x + 1), markA(x);
    }
    x = 64;
    while (!A[x] && !B[x] && x > 0) x--;
    while (x >= 0) printf("%d", (int)(A[x] || B[x])), x--;
    putchar(10);
    return 0;
}