反转一点

Question

我没能找到一个简单地反转一点的 common-lisp 函数（或宏）。有对位数组进行操作的函数，以及对数字进行操作的逻辑函数，但这些似乎涉及对单个位变量进行反转的额外步骤。暂定的解决方案是

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

哪个可行，但我想知道是否有更优雅或更简单的解决方案。

Answer 1

按位运算有很多运算符：

例如你可以使用

(logxor bit 1)

如果该位为 1，这将为您提供 0，如果该位为 0，则为您提供 1：

(logxor 0 1) ; => 1
(logxor 1 1) ; => 0

当然你可以把bit部分作为第二个参数：

(logxor 1 bit)

奖金:

也许你可以创建一个函数并使用类型声明对其进行优化:

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

在运行 (disassemble 'invert) 之后，我在 SBCL 上得到了以下结果：

没有类型声明：

; 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

WITH 类型声明

; 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

在我看来，类型声明节省了一些操作。

让我们来衡量一下差异：

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

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

现在运行:

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

输出：

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

同时运行:

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

输出：

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

似乎类型声明使函数的速度提高了一倍。必须注意，调用 invert 可能会抵消性能提升，除非您使用 (declaim (inline invert))。来自 CLHS:

inline specifies that it is desirable for the compiler to produce inline calls to the functions named by function-names; that is, the code for a specified function-name should be integrated into the calling routine, appearing ``in line'' in place of a procedure call.

反转一点

Inversion of a bit

common-lisp

bit

logical-operators