乘法、加法、或、异或、非...的组合可以对整数的二进制数字产生排列作用吗？

Question

设置： 考虑整数，如 int8（或 int16、int32、int64）。 每个整数都是 8 个二进制数字的序列，例如7 = 00000111。 这些数字上的 8 个字母的排列有简单、自然的作用。 最简单的例子是循环移位 - 大多数编程语言都支持循环移位。

问题：是否有其他排列的示例可以通过一个指令或指令组合来实现，例如乘以某物、加某物、与 smth 异或、或与 smth 、 not 等（即支持的那些指令）在大多数编程语言中，甚至在汇编语言中）？

澄清一下：我正在搜索一个或一组命令，以便它将充当所有二进制序列的排列。 IE。当您将其应用于 ANY(!) int8 "x" 时 - 生成的序列将是数字“x”的排列 - 即“1”和“0”的数量将与输入“x”中的数量相同。

反面例子 运算 - 乘以“3”（溢出时 - 取余数） - 作为 int8 上的双射，但不是排列，因为它不保留“1”和“0”的数量，即意味着输入“x”和输出“3x”不是彼此的排列。 （例如 3 * 1 = 3 = (00000111) - 这里是三个“1”，而输入仅包含一个“1”：(00000001)。

正例操作-循环移位。输入“x”，输出“shift-x” - 显然是二进制数字的排列。

问题的宽松版本：如果存在这样的例子，它们仅对包含4个数字“1”的数字子集充当排列（即子集-通过排列保留），那将会很有趣。例如，有 28 = $C^{2}_{8}$ 个数字，其中两位数字等于“1” - 是否有任何指令（指令序列）作用于该整数子集作为排列？

问题的概括：将 2 个后续数字组合在一个符号 int8 中 - 将是一系列 4 符号 ABCD，其中每个符号可以是 00、01、10、11。我们可以对此类符号上的 $S_4$ 操作的操作实现提出同样的问题。等等。

动机：在研究数学中，有时我们需要用排列进行计算实验，但由于 n!成长很快，我们的能力有限。如果有一些快速方法可以处理至少 S_8、S_16、S_32、S_64：int8、int16、int32、int64 - 这可能对某些问题有所帮助。

Answer 1

至少你可以表达任意排列

(i8, i7, i6, i5, i4, i3, i2, i1)

通过写：

y = ((x & 1) << i1) | ((x & 2) << (i2-1))
  | ((x & 4) << (i3-2))| ((x & 8) << (i4-3))
  | ((x & 16) << (i5-4)) | ((x & 32) << (i6-5))
  | ((x & 64) << (i7-6))| ((x & 128) << (i8-7));

(x & poweroftwo)

部分选择

x

的一点，

<< (i - j)

部分将其从旧位置 j 移动到新位置 i。

按位或

|

运算符组合所有各个位。事实上，在这种情况下，一个简单的

+

会做与

|

相同的事情。

如果一个特定的排列有更多的“逻辑”，那么你可能可以比单独移动每个位更简洁地描述这个排列。

例如，如果排列是两个不相交循环的并集，那么您可以执行两个循环移位并将它们重新组合，这比组合 8 个位移位的写入（和执行）时间要短。

事实上，所有排列都可以分解为不相交循环的并集，并且在大多数情况下，这应该会导致比上面的公式更具表现力的公式。

但是有8个！ = 8 个元素的 40320 种可能排列，并且 8 个元素的随机排列中平均循环数约为 3。因此，对于大多数排列，您不能期望公式太紧凑。

您可能有兴趣阅读柯尔莫哥洛夫复杂度，这是一个精确地描述数学对象“逻辑性/易于描述程度”而发明的概念。