Qual è il modo migliore per convertire i bit binari (potrebbe essere un elenco di 0/1, ad esempio) in numeri in modo reversibile. Ho scritto un predicato nativo in swi, ma c'è una soluzione migliore? migliori salutipredicato reversibile "da binario a numero"
risposta
Usa CLP (FD) i vincoli, ad esempio:
:- 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.
esempio esegue la query:
?- 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.
La soluzione
Questa risposta cerca di fornire un predicato binary_number/2
che presenta sia logical-purity sia le migliori proprietà di terminazione. Ho usato when/2
per impedire a query come canonical_binary_number(B, 10)
di andare in loop infinito dopo aver trovato la prima (unica) soluzione. C'è un trade-off, naturalmente, il programma ha obiettivi ridondanti ora.
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).
La purezza e la cessazione
ho sostengono che questo predicato presenta logical-purity dalla costruzione. Spero di aver capito bene da queste risposte: one, two e three.
Qualsiasi obiettivo con argomenti appropriati termina. Se gli argomenti devono essere controllati, il modo più semplice per raggiungere questo obiettivo è utilizzare il built-in 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
Esempio interroga
?- 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 .
'numeri binari (L, -1)' loop – false
È fuori dal dominio del secondo argomento. Posso aggiungere alcune condizioni come 'length (_, Number)' e verranno lanciate eccezioni. –
.... o aggiungi 'when (ground (Number), Number> = 0)' a 'binary_predicate/2'. –
giocare con bit ...
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 = []).
Ecco la soluzione a cui stavo pensando, o meglio, quello che speravo esistesse.
:- 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).
Questa soluzione termina anche per le query come:
?- Bs = [1|_], N #=< 5, binary_number(Bs, N).
Questo è un modo semplice ed elegante per risolvere il problema di terminazione (+1) ed evitare l'esponenziazione (:)). – lurker
Non capisco lo scopo di 'M'. Non puoi rimuoverlo e sostituirlo in 'M #> = N1' di' N'? – Fatalize
@Fatalize: 'M', quindi il 4o argomento è necessario per garantire che il predicato sia realmente reversibile. È la variabile originale ... – false
- 1. Da binario a intero -> Erlang
- 2. Python: Conversione da binario a stringa
- 3. piattaforma di calcolo reversibile
- 4. Numero di 1s in un numero binario
- 5. Conversione da binario a char in C
- 6. dati core molti-a-molti - domanda predicato
- 7. numero intero binario in output in php
- 8. Da un predicato induttivo alla lista A -> Lista A -> bool
- 9. Python: binario a decimale conversione
- 10. dividere un iteratore da un predicato
- 11. Avviso di predicato discontinuo da GNU Prolog
- 12. Animazione looped, reversibile utilizzando Core Animation
- 13. intero a binario Erlang
- 14. file binario a stringa
- 15. Semaforo binario rispetto a ReentrantLock
- 16. Algoritmo reversibile shuffle utilizzando una chiave
- 17. Lettura file binario da URLConnection
- 18. Acquisizione dell'output binario da Process.StandardOutput
- 19. Converti UUID in/da binario nel nodo
- 20. da binario a stringa, meglio di un dizionario?
- 21. Perché questa conversione da stringa a binario non funziona?
- 22. Come convertire da file binario a oggetto rilocabile e viceversa?
- 23. predicato IndexOf?
- 24. Combina predicato XPATH con posizione
- 25. Come convertire il numero intero nel vettore binario?
- 26. Conversione da numero intero a BigInteger
- 27. Conversione da numero intero a Java
- 28. Conversione da stringa a numero intero
- 29. Grafici Google HTML da sinistra a numero
- 30. Conversione di un numero binario con una lunghezza fissa
Quale dovrebbe essere la risposta per la seguente query: 'binary_number (B, -5) .': un'eccezione come * errore Domain: \ 'not_less_than_zero 'atteso, trovato \' -5' * ** o ** fallimento ('no' /' false')? –
@TudorBerariu: Come ti piace. Sia l'errore che l'errore vanno bene. (A proposito, non ho letto la tua domanda prima, devi @ me) – false