10

以可逆方式将二进制位（例如，它可能是 0/1 的列表）转换为数字的最佳方法是什么？我在 swi 中写了一个本地谓词，但有更好的解决方案吗？最好的祝福

4

4 回答 4

11

使用 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.
于 2010-11-16T15:34:10.410 回答
8

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

:- 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).
于 2015-02-10T22:03:46.140 回答
4

解决方案

该答案旨在提供一个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 .
于 2015-01-18T23:01:29.120 回答
1

玩比特...

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 = [] ).
于 2015-02-05T08:32:16.717 回答