给定一个二进制字符串，也就是说它只包含 0 和 1(零的数量等于 1 的数量(我们需要通过交换一些位来使这个字符串成为替代字符序列，我们的目标是最大限度地减少数量交换。
例如，对于字符串"00011011"，最小交换次数为 2，一种方法是：
1( 交换位 ： 000110 11--->> 000101 11
2( 交换位(第一次交换后(：0 0 0101 1 --->> 0 1 010101
请注意，如果我们得到字符串"00101011"，我们可以将其转换为以 0 开头的替代字符串(需要 3 次交换(，也可以转换为以 1 开头的替代字符串(需要一次交换 - 第一个和最后一个位(。
因此，在这种情况下，最小值为一次交换。
最终目标是返回给定的 1 和 0 字符串的最小交换次数。 解决它最有效的方法是什么？
琐碎的东西是微不足道的。
- xor 你的序列与
010101010….注意：如果序列已经"正确"，你会得到一个全0位流(如果你不关心你是以0还是1开头，也可以使用反向流(。XOR在现代CPU上非常高效。我可以在至强上一次做 512 位，我认为这需要 2 个周期。
数 - 一数(#ones(。在现代 x87 和许多其他 ISA 上，有一个 POPCNT 指令使其非常高效。吞吐量一个，在我的 CPU 上一次 64 位。
- 所需的隔夜利息为 #ones/2(显而易见(或 #zeros/2，以较低者为准。
注意：本网站上发布的代码是CC-by-SA。这意味着，当您在软件、家庭作业、考试或作业中使用它时，法律要求您声明此答案的 URL 和我的用户名。