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

Question

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

描述:

您将二进制字符串作为输入.

输出的第一位与输入的第一位相同.

如果输入字符串的索引处的位与输入字符串中前一个索引处的位相同,则此后的每个位都为0.否则,它是1.

例如,

输入:00011000001010100001001000010011

输出:00010100001111110001101100011010

这是一个简单的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).例如,如果将changeBinary函数应用于上面的字符串32次以上,它将返回原始值.

有没有人曾经遇到过这个问题,如果有的话,你知道有关它的任何其他信息吗？

在我看来,这是一个如此简单和基本的东西,有人必须更深入地研究它.

任何反馈将不胜感激.

Answer 1

知道这是x ^ (x << 1)在BigInteger上(或者,如果你限制字符串的长度,同样的东西,但是在固定大小的整数上),也可能是有趣的,也可以描述为clmul(x, 3).

无进行乘法,基本上就像正常乘法,但不是添加你对它们进行异或的部分乘积,而是具有一些相当不错的属性,例如可交换和关联.缔合性能是特别感兴趣,因为它可以让你轻松推理用什么构成本身的算法几次做:例如
changeBinary o changeBinary是clmul(clmul(x, 3), 3) = clmul(x, clmul(3, 3)) = clmul(x, 5)

它是3的无进位乘法也解释了为什么它在经常应用时"撤消"自身,因为3的无进位乘法逆是所有位设置的数,其中32位是0xffffffff,可以形成为3 ³¹(无进位取幂).这也取决于无进位方形与"位扩展" 的等价性,因此它需要一个字符串abcd到a0b0c0d,因此clpow(3, 32) = 1- 5个扩展已经将这些位扩展得如此之远以至于只剩下原始的lsb,休息不适合32位数字.

并且这也提供了更快的反转,因为所有位设置的数字可以分解为少量(无进位)因子:

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)