能否通过基础指令实现整数二进制位置换？含子集与泛化场景

设定 #

以int8（或int16、int32、int64）类型整数为例，每个整数对应8位二进制序列，如7对应00000111。8个元素的置换群可对这些二进制位产生自然作用，循环移位是最典型的例子，且多数编程语言均支持该操作。

核心问题 #

除循环移位外，是否存在其他置换操作可通过乘法、加法、异或、或、非等多数编程语言及汇编层面支持的单一或组合指令实现？

明确要求 #

需找到单一或组合指令，使其对所有二进制序列都能实现置换效果——即对任意int8类型的x，操作后的二进制序列是x的二进制位置换，1和0的数量与输入完全一致。

示例说明 #

• 反例：乘以3（溢出时取余）操作虽在int8上是双射，但并非置换：输入1（00000001，含1个1），输出3（00000111，含3个1），未保留1和0的数量。
• 正例：循环移位操作，输入x得到移位后的结果，显然是二进制位的置换。

扩展问题 #

问题放松版 #

是否存在仅对特定子集（如含4个1的数，或C₈²=28个含2个1的数）实现置换的指令序列？

问题泛化 #

将int8的每2位合并为一个符号（可取00、01、10、11），得到4符号序列ABCD，探讨能否通过基础指令实现S₄群对这些符号的置换作用，以此类推。

动机 #

数学研究中常需开展置换相关计算实验，但n!增长过快限制了实验规模。若能快速实现S₈、S₁₆、S₃₂、S₆₄对应的int8/16/32/64位置换，将助力相关研究。

更多背景 #

原讨论围绕Santa 2023竞赛中的位操作优化展开，参与者探讨了如何利用基础指令实现高效的二进制位置换，以解决大规模组合优化问题，其中提到了通过位运算组合实现特定置换的尝试，以及这类操作在竞赛和数学研究中的应用价值。

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