Java 异或运算

Question

我遇到了这个问题，其中给出了所有程序，只排除了一段逻辑。下列问题的缺失行可以填写什么？

问题陈述

杰克和丹尼尔是朋友。他们想加密他们的谈话，这样他们就可以避免被侦探机构拦截。所以他们发明了一种新的密码。每条消息都被编码为长度为 N 的二进制表示形式 B。然后被写下K次，移位0,1,...,K−1位。如果 B=1001010 和 K=4 它看起来像：

然后计算每一列的异或并记下来。这个数字叫做S。例如，对上述示例中的数字进行异或运算会导致

1110100110

然后将编码后的消息S和K发送给大牛

Jack正在使用这个编码算法，并要求Daniel实现一个解码算法。你能帮丹尼尔实现这个吗？

输入格式

第一行包含两个整数N和K。
第二行包含长度为N+K−1的字符串S，由1和0组成。

输出格式

长度为 N 的解码消息，由 1 和 0 组成。

约束

1≤N≤10^6,
1≤K≤10^6
|S|=N+K−1
保证S正确

样本输入#00

   7 4
   1110100110

示例输出#00

样本输入#01

   6 2
   1110001

示例输出#01

输入#00 的解释

输入#01 的解释

101111
 101111
-------
1110001

import java.io.*;

public class Solution {

    public static void solve(Input in, PrintWriter out) throws IOException {
        int n = in.nextInt();
        int k = in.nextInt();
        char[] c = in.next().toCharArray();
        int x = 0;
        char[] ans = new char[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = (char) (((c[i] - '0') ^ x) + '0');// I understand we are converting the character into integer (c[i] - '0') then xoring it with x which is holding 0 and then again adding '0' to convert back it into character.
            x ^= ans[i] - '0';// But why are we doing this!!. From this line onward things are not clear.
            if (i >= k - 1) {
                ****FILL THE MISSING LINE HERE****

            }
        }
        out.println(ans);
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
        out.close();
    }

    static class Input {
        BufferedReader in;
        StringBuilder sb = new StringBuilder();

        public Input(BufferedReader in) {
            this.in = in;
        }

        public Input(String s) {
            this.in = new BufferedReader(new StringReader(s));
        }

        public String next() throws IOException {
            sb.setLength(0);
            while (true) {
                int c = in.read();
                if (c == -1) {
                    return null;
                }
                if (" \n\r\t".indexOf(c) == -1) {
                    sb.append((char)c);
                    break;
                }
            }
            while (true) {
                int c = in.read();
                if (c == -1 || " \n\r\t".indexOf(c) != -1) {
                    break;
                }
                sb.append((char)c);
            }
            return sb.toString();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }
}

Answer 1

注意：请阅读解释，简单地通过复制粘贴答案来解决问题是没有用的。

你可以利用的约束是

The first bit is untouched by the encryption algorithm.

确实是因为所有 "masks" 都至少向右移动了一位。所以你可以假设加密部分的第一位也是解密内容的第一位。

现在您知道了第一位，您可以轻松地重构第二位，因为它只是与我们已知的第一位进行 xor 运算。所以知道我们可以计算出第二个。

第三位与第一位和第二位异或，所以基本上做的是维护一个值，该值是所有已经获得的值的异或，并将其与下一个值异或。初始值为零。

示例：

获取第一个样本输入：

1110100110

我们可以推导出第一个位是1。所以现在我们知道第二位的掩码的形式是：

       1110100110
mask    1????????
result 10

现在我们知道第三位的掩码是 1 和 0 的异或，因此 1.

       1110100110
mask    11???????
result 100

迭代最终会导致：

index      0123456789       
data       1110100110
submasks    1001010
             1001010
              1001010
mask       0111??????
result     1001??????

现在在 k-1 次迭代后，不再有额外的子掩码，事实上：一个只写 k 倍的数据作为结果，k-1 倍的子掩码。所以现在我们不再对新数据进行异或：我们只对结果的最后 k 位进行异或，这可以通过 unxoring （或简单地 xoring) 结果的位 k 向左。

对于下一个掩码，我们因此 xor 我们的状态（掩码的最后一位）与结果的最后一位（1）和第一个结果的一部分 (1)，这意味着状态保持不变 (1)：

index      0123456789
data       1110100110
submasks    1001010
             1001010
              1001010
mask       01111?????
result     10010?????

现在我们对最后一个结果位 (0) 和第二个结果位 (0) 进行异或：

index      0123456789
data       1110100110
submasks    1001010
             1001010
              1001010
mask       011111????
result     100101????

对于下一个，我们与最后一个 (1) 和第三个 (0) 异或，因此我们交换了状态。通过继续执行此过程，我们最终以：

index      0123456789
data       1110100110
submasks    1001010
             1001010
              1001010
mask       0111110???
result     1001010???

现在我们对剩余的位不再感兴趣，所以我们终止。

必须修改什么？

在 if 部分，我们还需要 xor (^) 第 i-(k-1) 位：

if (i >= k - 1) {
    x ^= ans[i-(k-1)] - '0';
}

Java 异或运算

Java XOR operation

java

algorithm

bit-manipulation

xor

bitwise-xor