交叉位运算两个整数

Question

我目前正在尝试实现一个非常简单的遗传算法示例。

在某一点上，您必须使用两个数字（父母）进行“交叉”（生物学），以获得一个“孩子”。

您可以在此处找到Cross-Over的解释：

如何“交叉”两个字符串（1234和abcd-> 12cd和ab34）

（第二个插图，更容易的“单点”Cross-Over是我正在尝试的。）

染色体（父母和孩子）是数字，但“Cross-Over”将是一个位运算。

我为其中一个“染色体”找到了解决方案，如下所示：

• 将X位向右移动（>>> 运算符）
• 然后再次将位移X个位置，但这次是向左移动（<< 运算符）

因此，这将保留一个染色体的末尾，并用0填充开头。

但我不知道如何解决另一个染色体的问题，然后进行交叉。

（可能是一次异或，我保留了染色体的开头/结尾，并用0填充其余部分。）

还是应该从另一个角度来解决这个问题？

- m_vdbeek

---

你是否总是知道你的两个输入作为数字的大小（例如，16位整数）？ - David

是的，它们始终是16位整数。可以修改的一件事是交叉百分比。例如，75％将保留父母A的前4个（25％）位，然后跟随来自父母B的12（75％）位。 - m_vdbeek

Answer 1

如果交叉分数为p（例如，p = .25），则应该这样操作：

mask1 = ((0xffff >> 16*p) << 16*p)
mask2 = 0xffff ^ mask1
output1 = (input1 & mask1) ^ (input2 & mask2)
output2 = (input1 & mask2) ^ (input2 & mask1)

一些注释：

• 这只是伪代码。你可能需要在其中添加一些类型转换。
• 这个代码片段对待p的方式与你在上面的评论中所描述的不同。（只需将p替换为1-p即可得到你对p的定义。）

- David

---

哇，我的脑袋炸了！我需要一些时间来理解这段代码。^^ 谢谢你的快速回答！ - m_vdbeek

将0xffff模式向右移动然后再向左移动，与您在描述中所说的做法是相同的。因此，如果p = .5，则在右移位之后，mask1将最终变为0xff，然后在左移位之后变为0xff00。将其与0xffff异或可得到mask2中未打开的所有位。 - David

Answer 2

一个天真的方法是使用4个本地变量：

int chromatid1Start;
int chromatid1End;
int chromatid2Start;
int chromatid2End;

然后，将传入的chromatid1分配给前两个变量，将chromatid2分配给后两个变量。

chromatid1Start = chromatid1;
chromatid1End = chromatid1;
chromatid2Start = chromatid2;
chromatid2End = chromatid2;

对于 Start 染色体变量，在交叉点之前执行右移操作，然后左移相同的量。对于 End 染色体变量，在交叉点之前执行左移操作，然后右移相同的量。

chromatid1Start = (chromatid1Start >> 16 * crossoverPercent) << 16 * crossoverPercent;
chromatid1End = (chromatid1End << 16 * (1 - crossoverPercent)) >> 16 * (1 - crossoverPercent);
chromatid2Start = (chromatid2Start >> 16 * crossoverPercent) << 16 * crossoverPercent;
chromatid2End = (chromatid2End << 16 * (1 - crossoverPercent)) >> 16 * (1 - crossoverPercent);

有了这个，你可以将一个的开头与另一个的结尾相连：

int daughterChromatid1 = chromatid1Start + chromatid2End;
int daughterChromatid2 = chromatid2Start + chromatid1End;

- saluce