可逆的“二进制到数字”谓词

Question

以可逆的方式将二进制位（例如，可能是 0/1 的列表）转换为数字的最佳方法是什么？我已经用 swi 编写了一个本机谓词，但是有更好的解决方案吗？ 此致

Answer 1

使用 CLP(FD) 约束，例如：

:- use_module(library(clpfd)).

binary_number(Bs0, N) :-
        reverse(Bs0, Bs),
        foldl(binary_number_, Bs, 0-0, _-N).

binary_number_(B, I0-N0, I-N) :-
        B in 0..1,
        N #= N0 + B*2^I0,
        I #= I0 + 1.

示例查询：

?- binary_number([1,0,1], N).
N = 5.

?- binary_number(Bs, 5).
Bs = [1, 0, 1] .

?- binary_number(Bs, N).
Bs = [],
N = 0 ;
Bs = [N],
N in 0..1 ;
etc.

Answer 2

这是我想到的解决方案，或者更确切地说是我希望存在的解决方案。

:- use_module(library(clpfd)).

binary_number(Bs, N) :-
   binary_number_min(Bs, 0,N, N).

binary_number_min([], N,N, _M).
binary_number_min([B|Bs], N0,N, M) :-
   B in 0..1,
   N1 #= B+2*N0,
   M #>= N1,
   binary_number_min(Bs, N1,N, M).

该解决方案也会因以下查询而终止：

?- Bs = [1|_], N #=< 5, binary_number(Bs, N).

Answer 3

解决方案

该答案旨在提供一个谓词 binary_number/2 来表示 逻辑纯度 和最佳终止属性。我使用了 when/2 来阻止像 canonical_binary_number(B, 10) 这样的查询在找到第一个（唯一的）解决方案后进入无限循环。当然，这是一个权衡，该计划现在有多余的目标。

canonical_binary_number([0], 0).
canonical_binary_number([1], 1).
canonical_binary_number([1|Bits], Number):-
    when(ground(Number),
         (Number > 1,
          Pow is floor(log(Number) / log(2)),
          Number1 is Number - 2 ^ Pow,
          (   Number1 > 1
           -> Pow1 is floor(log(Number1) / log(2)) + 1
           ;  Pow1 = 1
         ))),
    length(Bits, Pow),
    between(1, Pow, Pow1),
    length(Bits1, Pow1),
    append(Zeros, Bits1, Bits),
    maplist(=(0), Zeros),
    canonical_binary_number(Bits1, Number1),
    Number is Number1 + 2 ^ Pow.

binary_number(Bits, Number):-
    canonical_binary_number(Bits, Number).
binary_number([0|Bits], Number):-
    binary_number(Bits, Number).

纯度和终止

我声称这个谓词呈现。我希望我从这些答案中得到了正确的答案：一个，两个和三个。

任何具有适当参数的目标都会终止。如果需要检查参数，实现此目的的最简单方法是使用内置的 length/2：

binary_number(Bits, Number):-
    length(_, Number),
    canonical_binary_number(Bits, Number).

?- binary_number(Bits, 2+3).
ERROR: length/2: Type error: `integer' expected, found `2+3'
   Exception: (6) binary_number(_G1642009, 2+3) ? abort
% Execution Aborted
?- binary_number(Bits, -1).
ERROR: length/2: Domain error: `not_less_than_zero' expected, found `-1'
   Exception: (6) binary_number(_G1642996, -1) ? creep

示例查询

?- binary_number([1,0,1|Tail], N).
Tail = [],
N = 5 ;
Tail = [0],
N = 10 ;
Tail = [1],
N = 11 ;
Tail = [0, 0],
N = 20 .

?- binary_number(Bits, 20).
Bits = [1, 0, 1, 0, 0] ;
Bits = [0, 1, 0, 1, 0, 0] ;
Bits = [0, 0, 1, 0, 1, 0, 0] ;
Bits = [0, 0, 0, 1, 0, 1, 0, 0] ;
Bits = [0, 0, 0, 0, 1, 0, 1, 0, 0] .

?- binary_number(Bits, N).
Bits = [0],
N = 0 ;
Bits = [1],
N = 1 ;
Bits = [1, 0],
N = 2 ;
Bits = [1, 1],
N = 3 ;
Bits = [1, 0, 0],
N = 4 ;
Bits = [1, 0, 1],
N = 5 .

Answer 4

玩比特...

binary_number(Bs, N) :-
    var(N) -> foldl(shift, Bs, 0, N) ; bitgen(N, Rs), reverse(Rs, Bs).

shift(B, C, R) :-
    R is (C << 1) + B.

bitgen(N, [B|Bs]) :-
    B is N /\ 1 , ( N > 1 -> M is N >> 1, bitgen(M, Bs) ; Bs = [] ).

Answer 5

可以使用递归，而不是 reverse/2：

binary_list_int([1|T], I) :-
    (   integer(I)
    ->  I @>= 1
    ;   var(I)
    ),
    binary_list_int_(T, 1, _, 1, I, I).

binary_list_int_([], H, 1, _M, _N, I) :-
    binary_list_int_digit_(H, 1, I).
binary_list_int_([H|T], P, U1, M, N, I) :-
    M1 is M * 2,
    % Prevent increasing into infinity
    (   nonvar(N)
    ->  N @>= M1
    ;   true
    ),
    binary_list_int_(T, H, U, M1, N, I0),
    U1 is U * 2,
    binary_list_int_digit_(P, U1, B),
    I is I0 + B.

binary_list_int_digit_(0, _, 0).
binary_list_int_digit_(1, U, U).

swi-prolog 中的结果：

% Terminates
?- binary_list_int(Bs, 5).
Bs = [1, 0, 1] ;
false.

% Prevents leading zero
?- between(0, 5, I), binary_list_int(Bs, I).
I = 1,
Bs = [1] ;
I = 2,
Bs = [1, 0] ;
I = 3,
Bs = [1, 1] ;
I = 4,
Bs = [1, 0, 0] ;
I = 5,
Bs = [1, 0, 1] ;
false.

% No unwanted choicepoint, when providing list
?- binary_list_int([1,1,0,0,0], I).
I = 24.

?- binary_list_int(Bs, I).
Bs = [1],
I = 1 ;
Bs = [1, 0],
I = 2 ;
Bs = [1, 1],
I = 3 ;
Bs = [1, 0, 0],
I = 4 ;
Bs = [1, 1, 0],
I = 6 ;
Bs = [1, 0, 1],
I = 5 ;
Bs = [1, 1, 1],
I = 7 ;
Bs = [1, 0, 0, 0],
I = 8 ;

% Prevents invalid input
?- binary_list_int(Bs, -5).
false.