Побитовые операции над целыми числами

В компьютере целое число представлено в виде двоичного числа — последовательности битов (цифр, которые могут быть равны нулю или единице). Концептуально последовательность битов бесконечна слева, причём старшие биты состоят либо только из нулей, либо только из единиц. Побитовая операция выполняется над отдельными битами такой последовательности. Например, сдвиг перемещает всю последовательность влево или вправо на одну или несколько позиций, сохраняя тот же шаблон.

Побитовые операции в Emacs Lisp применяются только к целым числам.

Функция: ash integer count

ash (арифметический сдвиг) сдвигает биты в integer влево на count позиций или вправо, если count отрицательно. При сдвиге влево справа добавляются нулевые биты; при сдвиге вправо отбрасываются крайние правые биты. Если рассматривать операцию над целыми числами, ash умножает integer на 2**count, а затем преобразует результат в целое число, округляя его вниз, в сторону минус бесконечности.

Вот примеры ash: шаблон битов сдвигается на одну позицию влево и вправо. В этих примерах показаны только младшие биты двоичного шаблона; все предшествующие биты совпадают со старшим показанным битом. Как видно, сдвиг влево на одну позицию эквивалентен умножению на два, а сдвиг вправо на одну позицию эквивалентен делению на два с последующим округлением в сторону минус бесконечности.

(ash 7 1) ⇒ 14
;; Decimal 7 becomes decimal 14.
...000111
     ⇒
...001110

(ash 7 -1) ⇒ 3
...000111
     ⇒
...000011

(ash -7 1) ⇒ -14
...111001
     ⇒
...110010

(ash -7 -1) ⇒ -4
...111001
     ⇒
...111100

Вот примеры сдвига влево или вправо на два бита:

                  ;         binary values
(ash 5 2)         ;   5  =  ...000101
     ⇒ 20         ;      =  ...010100
(ash -5 2)        ;  -5  =  ...111011
     ⇒ -20        ;      =  ...101100

(ash 5 -2)
     ⇒ 1          ;      =  ...000001

(ash -5 -2)
     ⇒ -2         ;      =  ...111110

Функция: lsh integer count

lsh, сокращение от логический сдвиг, сдвигает биты в integer влево на count позиций или вправо, если count отрицательно, заполняя освободившиеся биты нулями. Если count отрицательно, то integer должно быть либо fixnum, либо положительным bignum, а lsh обрабатывает отрицательный fixnum как беззнаковое число, вычитая перед сдвигом удвоенное значение most-negative-fixnum, что даёт неотрицательный результат. Это странное поведение восходит к временам, когда Emacs поддерживал только fixnum; сегодня лучше использовать ash.

Поскольку lsh ведёт себя как ash, за исключением случаев, когда и integer, и count отрицательны, в следующих примерах рассматриваются эти исключительные случаи. В примерах предполагаются 30-битные fixnum.

                 ;      binary values
(ash -7 -1)      ; -7 = ...111111111111111111111111111001
     ⇒ -4        ;    = ...111111111111111111111111111100
(lsh -7 -1)
     ⇒ 536870908 ;    = ...011111111111111111111111111100

(ash -5 -2)      ; -5 = ...111111111111111111111111111011
     ⇒ -2        ;    = ...111111111111111111111111111110
(lsh -5 -2)
     ⇒ 268435454 ;    = ...001111111111111111111111111110

Функция: logand &rest ints-or-markers

Эта функция возвращает побитовое И аргументов: n-й бит результата равен 1 тогда и только тогда, когда n-й бит равен 1 во всех аргументах.

Например, если использовать 4-битные двоичные числа, побитовое И чисел 13 и 12 равно 12: 1101 в сочетании с 1100 даёт 1100. В обоих двоичных числах два левых бита равны 1, поэтому два левых бита возвращаемого значения также равны 1. Однако каждый из двух правых битов равен 0 хотя бы в одном из аргументов, поэтому два правых бита возвращаемого значения равны 0.

Следовательно,

(logand 13 12)
     ⇒ 12

Если logand вызвана без аргументов, она возвращает значение −1. Это число является нейтральным элементом для logand, поскольку его двоичное представление состоит только из единиц. Если logand передан только один аргумент, она возвращает этот аргумент.

                   ;        binary values

(logand 14 13)     ; 14  =  ...001110
                   ; 13  =  ...001101
     ⇒ 12         ; 12  =  ...001100

(logand 14 13 4)   ; 14  =  ...001110
                   ; 13  =  ...001101
                   ;  4  =  ...000100
     ⇒ 4          ;  4  =  ...000100

(logand)
     ⇒ -1         ; -1  =  ...111111

Функция: logior &rest ints-or-markers

Эта функция возвращает побитовое включающее ИЛИ аргументов: n-й бит результата равен 1 тогда и только тогда, когда n-й бит равен 1 хотя бы в одном из аргументов. Если аргументов нет, результат равен 0 — нейтральному элементу этой операции. Если logior передан только один аргумент, она возвращает этот аргумент.

                   ;        binary values

(logior 12 5)      ; 12  =  ...001100
                   ;  5  =  ...000101
     ⇒ 13         ; 13  =  ...001101

(logior 12 5 7)    ; 12  =  ...001100
                   ;  5  =  ...000101
                   ;  7  =  ...000111
     ⇒ 15         ; 15  =  ...001111

Функция: logxor &rest ints-or-markers

Эта функция возвращает побитовое исключающее ИЛИ аргументов: n-й бит результата равен 1 тогда и только тогда, когда n-й бит равен 1 в нечётном количестве аргументов. Если аргументов нет, результат равен 0 — нейтральному элементу этой операции. Если logxor передан только один аргумент, она возвращает этот аргумент.

                   ;        binary values

(logxor 12 5)      ; 12  =  ...001100
                   ;  5  =  ...000101
     ⇒ 9          ;  9  =  ...001001

(logxor 12 5 7)    ; 12  =  ...001100
                   ;  5  =  ...000101
                   ;  7  =  ...000111
     ⇒ 14         ; 14  =  ...001110

Функция: lognot integer

Эта функция возвращает побитовое дополнение аргумента: n-й бит результата равен единице тогда и только тогда, когда n-й бит в integer равен нулю, и наоборот. Результат равен −1 − integer.

(lognot 5)
     ⇒ -6
;;  5  =  ...000101
;; becomes
;; -6  =  ...111010

Функция: logcount integer

Эта функция возвращает вес Хэмминга числа integer: количество единиц в его двоичном представлении. Если integer отрицательно, функция возвращает количество нулевых битов в его двоичном представлении в дополнительном коде. Результат всегда неотрицателен.

(logcount 43)     ;  43 = ...000101011
     ⇒ 4
(logcount -43)    ; -43 = ...111010101
     ⇒ 3