predicado reversível “binário para número”

Qual é a melhor maneira de converter bits binários (pode ser uma lista de 0/1, por exemplo) em números de forma reversível. Eu escrevi um predicado nativo em swi, mas existe melhor solução? Cumprimentos

Use as restrições CLP (FD), por exemplo:

 :- use_module(library(clpfd)). binary_number(Bs0, N) :- reverse(Bs0, Bs), foldl(binary_number_, Bs, 0-0, _-N). binary_number_(B, I0-N0, IN) :- B in 0..1, N #= N0 + B*2^I0, I #= I0 + 1. 

Exemplo de consultas:

 ?- 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. 

Aqui está a solução que eu estava pensando, ou melhor, o que eu esperava que existisse.

 :- 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). 

Esta solução também termina para consultas como:

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

A solução

Essa resposta procura fornecer um predicado binary_number/2 que apresente pureza lógica e as melhores propriedades de terminação. Eu usei when/2 para impedir que consultas como canonical_binary_number(B, 10) entrassem em loop infinito depois de encontrar a primeira solução (única). Há um trade-off, claro, o programa tem metas redundantes agora.

 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). 

Pureza e terminação

Eu afirmo que este predicado apresenta pureza lógica da construção. Espero que tenha acertado a partir dessas respostas: uma , duas e três .

Qualquer objective com argumentos apropriados é encerrado. Se os argumentos precisarem ser verificados, a maneira mais simples de conseguir isso é usando o 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 

Exemplo de consultas

 ?- 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 . 

brincando com pedaços …

 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 = [] ). 
    Intereting Posts