16位场景下c = m XOR (m循环左移a位)的逆运算求解方法

解法 #

核心原理 #

你遇到的问题本质是二元域（GF(2)）下的循环线性方程求解，公式c = m XOR ROL(m, a)（ROL指循环左移）的解存在且成对出现：m和m ^ 0xFFFF（即m按位取反），你已经排除全0、全1的特殊情况，只需取非全1的解即可。

通用推导步骤（以16位、a=1为例） #

1. 设16位数值的位序号从高到低为b₁₅（最高位）到b₀（最低位），循环左移1位后m变为b₁₄ b₁₃ ... b₀ b₁₅，因此c的每一位满足：

   cₖ = bₖ XOR bₖ₋₁ （k从15到1）
   c₀ = b₀ XOR b₁₅
   

2. 固定最高位b₁₅ = 0（排除全1解，全1解的最高位为1）
3. 从高位到低位逐位推导剩余位：

   bₖ₋₁ = cₖ XOR bₖ （k从15到1）
   

示例验证 #

用你给出的c值0101000001001011推导：

• c的各位值（从高到低）：0,1,0,1,0,0,0,0,0,1,0,0,1,0,1,1
• 固定b₁₅=0，依次推导得到所有位拼接结果为0011000000111001，和原始m完全一致。

扩展到任意a的情况 #

如果a不为1，只要a和16互质，都可以用类似的逐位递推方法求解即可。

内容的提问来源于stack exchange，提问作者dima9751