Inversion eines Bits

Question

Ich konnte keine allgemeine Lisp-Funktion (oder Makro) finden, die einfach ein Bit invertiert. Es gibt Funktionen, die an Bit-Arrays arbeiten, und logische Funktionen, die mit Zahlen arbeiten, aber diese scheinen zusätzliche Schritte für die Inversion einer einzelnen Bit-Variable zu beinhalten. Eine vorläufige Lösung ist

(define-modify-macro invertf (&rest args) 
    (lambda (bit) 
    (if (= bit 0) 1 0))) 

was funktioniert, aber ich frage mich, ob es eine elegantere oder einfachere Lösung gibt.

Answer 1

Es gibt eine Menge von Operatoren für bitweise Arithmetik:

Zum Beispiel können Sie verwenden

(logxor bit 1) 

Dies wird Ihnen 0, wenn das Bit 1 ist und 1, wenn das Bit 0 ist:

Natürlich können Sie den bit Teil als zweites Argument setzen:

(logxor 1 bit) 

Bonus:

Vielleicht können Sie eine Funktion machen und optimieren es mit einer Typdeklaration:

(defun invert (bit) 
    "Inverts a bit" 
    (declare (type bit bit)) 
    (logxor bit 1)) 

Nach (disassemble 'invert) Laufen bekam ich folgende Ergebnisse auf SBCL:

OHNE Typdeklaration:

; disassembly for INVERT 
; Size: 56 bytes. Origin: #x10059E97FC 
; 7FC:  498B4C2460  MOV RCX, [R12+96]    ; thread.binding-stack-pointer 
                   ; no-arg-parsing entry point 
; 801:  48894DF8   MOV [RBP-8], RCX 
; 805:  BF02000000  MOV EDI, 2 
; 80A:  488BD3   MOV RDX, RBX 
; 80D:  4883EC18   SUB RSP, 24 
; 811:  48896C2408  MOV [RSP+8], RBP 
; 816:  488D6C2408  LEA RBP, [RSP+8] 
; 81B:  B904000000  MOV ECX, 4 
; 820:  FF1425980B1020 CALL QWORD PTR [#x20100B98]  ; TWO-ARG-XOR 
; 827:  488B5DF0   MOV RBX, [RBP-16] 
; 82B:  488BE5   MOV RSP, RBP 
; 82E:  F8    CLC 
; 82F:  5D    POP RBP 
; 830:  C3    RET 
; 831:  0F0B10   BREAK 16      ; Invalid argument count trap 

MIT Typdeklaration

; disassembly for INVERT 
; Size: 25 bytes. Origin: #x1005767CA9 
; A9:  498B4C2460  MOV RCX, [R12+96]    ; thread.binding-stack-pointer 
                  ; no-arg-parsing entry point 
; AE:  48894DF8   MOV [RBP-8], RCX 
; B2:  488BD3   MOV RDX, RBX 
; B5:  4883F202   XOR RDX, 2 
; B9:  488BE5   MOV RSP, RBP 
; BC:  F8    CLC 
; BD:  5D    POP RBP 
; BE:  C3    RET 
; BF:  0F0B10   BREAK 16       ; Invalid argument count trap 

Es scheint mir, dass die Typdeklaration ein paar Operationen gespeichert.

Lassen Sie uns den Unterschied messen:

(defun invert (bit) 
    "Inverts a bit" 
    (declare (type bit bit)) 
    (logxor bit 1)) 

(defun invert-no-dec (bit) 
    "Inverts a bit" 
    (logxor bit 1)) 

Jetzt läuft:

(time (loop repeat 1000000 do (invert 1))) 

Ausgänge:

Evaluation took: 
    0.007 seconds of real time 
    0.005164 seconds of total run time (0.005073 user, 0.000091 system) 
    71.43% CPU 
    14,060,029 processor cycles 
    0 bytes consed 

Während des Laufens:

(time (loop repeat 1000000 do (invert-no-dec 1))) 

Ausgänge:

Evaluation took: 
    0.011 seconds of real time 
    0.011327 seconds of total run time (0.011279 user, 0.000048 system) 
    100.00% CPU 
    25,505,355 processor cycles 
    0 bytes consed 

Es scheint, die Typdeklaration so schnell die Funktion zweimal macht. Es ist zu beachten, dass der Aufruf an invert wahrscheinlich den Leistungszuwachs ausgleichen wird, es sei denn, Sie verwenden (declaim (inline invert)).Vom CLHS:

inline gibt an, dass es wünschenswert ist, dass der Compiler auf die Funktionen von Funktionsnamen genannt Inline-Anrufe zu erzeugen; Das heißt, der Code für einen angegebenen Funktionsnamen sollte in die aufrufende Routine integriert werden und anstelle eines Prozeduraufrufs "in Zeile" erscheinen.