algorithm - 这个算法有名字吗？ (我一直称其为changeBinary)

这个算法有名字吗（我一直叫它changeBinary）
说明：
以二进制字符串作为输入。
输出的第一位与输入的第一位相同。
如果输入字符串索引处的位与输入字符串上一个索引处的位相同，则之后的每个位都是0否则，是1。
例如，
输入：00011000010101000001000010011
输出：000101000111110001101100011010
下面是一个简单的javascript实现：

var changeBinary = function(binaryString){
  var output = binaryString[0] === '0' ? '0' : 1;
  for (var i = 1; i < binaryString.length; i++){
    var nextBit = binaryString[i] === binaryString[i - 1] ? '0' : '1';
    output += nextBit;
  }
  return output;
}

观察：
首先，如果继续将算法应用于字符串，它最终将返回其原始值其次，迭代次数似乎总是2的幂（包括2^0=1）。例如，如果对上面的字符串应用超过32次的changebinary函数，它将返回到原始值。
以前有人遇到过这种情况吗？如果是的话，你知道关于它的其他信息吗？
在我看来，这是一件非常简单和基本的事情，一定有人对它进行了更深入的研究。
任何反馈都将非常感谢。

最佳答案

可能有意思的是，这是一个大整数上的x ^ (x << 1)（或者，如果你限制字符串的长度，同样的事情，但在一个固定大小的整数上），也可以描述为clmul(x, 3)。
carryless乘法本质上与正规乘法类似，但它没有把部分乘积相加，而是具有一些相当好的性质，例如交换性和结合性。关联属性尤其令人感兴趣，因为它允许您很容易地思考将算法与自身组合在一起所做的事情：例如
changeBinary o changeBinary是clmul(clmul(x, 3), 3) = clmul(x, clmul(3, 3)) = clmul(x, 5)
它是3的carryless乘法，这也解释了为什么它在足够频繁的应用时“撤销”自己，因为3的carryless乘法逆是所有位都被设置的数字，32位是0xffffffff，可以形成331（carryless指数化）。这也遵循了无进位平方与“位扩展”的等价关系，因此它需要一个位串abcd到a0b0c0d，因此clpow(3, 32) = 1-5个扩展将位分散得如此之远，以至于只剩下原始lsb，其余的不适合32位数字。
这也提供了一个更快的反演，因为具有所有位集的数字可以分解为少量（carryless）因子：

3 x 5 x 17 x 257 x 65537 ...

一组因子，即位数的对数（四舍五入）。
由于x ^ (x >> 1)将数字转换为灰色代码，我想您可以将其称为“镜像”灰色代码在“镜像”中使用与因子相同的技巧将灰色代码转换回二进制代码：

x ^= x >> 1 // this is like a "mirror" of x = clmul(x, 3)
x ^= x >> 2 //                                         5
x ^= x >> 4 //                                        17
x ^= x >> 8
x ^= x >> 16

在这里，我们只需反转移位的方向即可得到：

x ^= x << 1
x ^= x << 2
x ^= x << 4
x ^= x << 8
x ^= x << 16

它是clmul(x, 0xffffffff)并且也被称为PS-XOR(x)

关于algorithm - 这个算法有名字吗？ (我一直称其为changeBinary)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48053736/