使用Prolog CLPFD为32位数字实现XOR功能

我尝试在Prolog CLPFD中实现高效的异或(XOR).这应该是简单的谓词,如:

xor(A, B, AxorB).

A,B,AxorB是自然数(用0表示)和AxorB是的结果A 的XOR B.

我的主要问题是效率.首先,我无法找到任何方法来对两个数字进行异或,而不将这些数字分成可以进一步处理/约束的单独部分,并且打破这些数字的过程(创建适当的约束然后解析它们)正在进行一些处理时间.其次,我不能提出任何有效的方法来"模拟"自然数字上的XOR函数,而不是在下面的第二个代码中给出.

让我们从我的第一个代码开始.这是最简单的XOR实现,它仅适用于1位值(0和1):

xor_1bit_values(A, B, AxorB) :-
    AxorB #= (A + B) mod 2.

要将其用于大于1的数字,必须将数字分成位:

xor_number(A, B, Result, Bits) :-
    Count is Bits - 1,
    xor_number(A, B, Result, Count, 0).
xor_number(A, B, Result, 0, Sum) :-
    xor_1bit_values(A, B, Xor),
    Result #= Xor + Sum.
xor_number(A, B, Result, Count, Sum) :-
    P is 2^Count,
    X #= A / P,
    Y #= B / P,
    xor_1bit_values(X, Y, Tmp),
    NewSum #= Sum + P*Tmp,
    NewCount is Count - 1,
    xor_number(A, B, Result, NewCount, NewSum).

样本输入和输出:

?- time(xor_number(123456789, 987654321, R, 32)).
% 943 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
R = 1032168868

现在,这对我的目的来说太慢了,因为在我的代码中我有时需要猜测A,B当我AxorB所有这些都应该是32位数字时.对于需要超过10位的数字,这可能会导致数百万的推论,这些推断似乎会呈现出潜在的增长.我使用最好的标签策略,XOR参数交换和其他技巧来加速计算.

所以,我试着做一些数学.我设计的是2位值(0,1,2,3)的XOR函数:

xor_2bit_values(A, B, Result) :-
    Result #= ((A + B*((-1)^A)) mod 4).

要在大于3的数字中使用它,代码类似于我之前提出的代码:

xor_number2(A, B, Result, Bits) :-
    Count is (Bits / 2) - 1,
    xor_number2(A, B, Result, Count, 0).
xor_number2(A, B, Result, 0, Sum) :-
    xor_2bit_values(A, B, Xor),
    Result #= Xor + Sum,
    !.
xor_number2(A, B, Result, Count, Sum) :-
    P is 4^Count,
    X #= A / P,
    Y #= B / P,
    xor_2bit_values(X, Y, Tmp),
    NewSum #= Sum + P*Tmp,
    NewCount is Count - 1,
    xor_number2(A, B, Result, NewCount, NewSum).

这似乎比第一个代码快了近50%.但是,对我来说,两倍的差异仍然太小.

所以,我的问题是:如何为32位数字实现高效的XOR？如果这在现代机器上是不可能的,你可以通过某种计算证明它,那么它也是我的问题的一个很好的答案.最终,我怎样才能最好地改进我的代码？也许你有一些想法如何处理数字而不会分开它们或如何以其他方式对数字进行异或？

附加信息:如果您碰巧尝试我的代码从三个参数或XOR猜测两个,那么因为可以自由地交换该函数的参数(来自其数学属性)我建议设置A为绑定变量B并且AxorB作为未绑定.CLPFD似乎以这种方式运作得最快.此外,最好的标签策略是labeling([bisect], [B,AxorB].