elisp: Bitwise Operations
3.8 Bitwise Operations on Integers
==================================
In a computer, an integer is represented as a binary number, a sequence
of “bits” (digits which are either zero or one). A bitwise operation
acts on the individual bits of such a sequence. For example, “shifting”
moves the whole sequence left or right one or more places, reproducing
the same pattern moved over.
The bitwise operations in Emacs Lisp apply only to integers.
-- Function: lsh integer1 count
‘lsh’, which is an abbreviation for “logical shift”, shifts the
bits in INTEGER1 to the left COUNT places, or to the right if COUNT
is negative, bringing zeros into the vacated bits. If COUNT is
negative, ‘lsh’ shifts zeros into the leftmost (most-significant)
bit, producing a positive result even if INTEGER1 is negative.
Contrast this with ‘ash’, below.
Here are two examples of ‘lsh’, shifting a pattern of bits one
place to the left. We show only the low-order eight bits of the
binary pattern; the rest are all zero.
(lsh 5 1)
⇒ 10
;; Decimal 5 becomes decimal 10.
00000101 ⇒ 00001010
(lsh 7 1)
⇒ 14
;; Decimal 7 becomes decimal 14.
00000111 ⇒ 00001110
As the examples illustrate, shifting the pattern of bits one place
to the left produces a number that is twice the value of the
previous number.
Shifting a pattern of bits two places to the left produces results
like this (with 8-bit binary numbers):
(lsh 3 2)
⇒ 12
;; Decimal 3 becomes decimal 12.
00000011 ⇒ 00001100
On the other hand, shifting one place to the right looks like this:
(lsh 6 -1)
⇒ 3
;; Decimal 6 becomes decimal 3.
00000110 ⇒ 00000011
(lsh 5 -1)
⇒ 2
;; Decimal 5 becomes decimal 2.
00000101 ⇒ 00000010
As the example illustrates, shifting one place to the right divides
the value of a positive integer by two, rounding downward.
The function ‘lsh’, like all Emacs Lisp arithmetic functions, does
not check for overflow, so shifting left can discard significant
bits and change the sign of the number. For example, left shifting
536,870,911 produces −2 in the 30-bit implementation:
(lsh 536870911 1) ; left shift
⇒ -2
In binary, the argument looks like this:
;; Decimal 536,870,911
0111...111111 (30 bits total)
which becomes the following when left shifted:
;; Decimal −2
1111...111110 (30 bits total)
-- Function: ash integer1 count
‘ash’ (“arithmetic shift”) shifts the bits in INTEGER1 to the left
COUNT places, or to the right if COUNT is negative.
‘ash’ gives the same results as ‘lsh’ except when INTEGER1 and
COUNT are both negative. In that case, ‘ash’ puts ones in the
empty bit positions on the left, while ‘lsh’ puts zeros in those
bit positions.
Thus, with ‘ash’, shifting the pattern of bits one place to the
right looks like this:
(ash -6 -1) ⇒ -3
;; Decimal −6 becomes decimal −3.
1111...111010 (30 bits total)
⇒
1111...111101 (30 bits total)
In contrast, shifting the pattern of bits one place to the right
with ‘lsh’ looks like this:
(lsh -6 -1) ⇒ 536870909
;; Decimal −6 becomes decimal 536,870,909.
1111...111010 (30 bits total)
⇒
0111...111101 (30 bits total)
Here are other examples:
; 30-bit binary values
(lsh 5 2) ; 5 = 0000...000101
⇒ 20 ; = 0000...010100
(ash 5 2)
⇒ 20
(lsh -5 2) ; -5 = 1111...111011
⇒ -20 ; = 1111...101100
(ash -5 2)
⇒ -20
(lsh 5 -2) ; 5 = 0000...000101
⇒ 1 ; = 0000...000001
(ash 5 -2)
⇒ 1
(lsh -5 -2) ; -5 = 1111...111011
⇒ 268435454
; = 0011...111110
(ash -5 -2) ; -5 = 1111...111011
⇒ -2 ; = 1111...111110
-- Function: logand &rest ints-or-markers
This function returns the bitwise AND of the arguments: the Nth bit
is 1 in the result if, and only if, the Nth bit is 1 in all the
arguments.
For example, using 4-bit binary numbers, the bitwise AND of 13 and
12 is 12: 1101 combined with 1100 produces 1100. In both the
binary numbers, the leftmost two bits are both 1 so the leftmost
two bits of the returned value are both 1. However, for the
rightmost two bits, each is 0 in at least one of the arguments, so
the rightmost two bits of the returned value are both 0.
Therefore,
(logand 13 12)
⇒ 12
If ‘logand’ is not passed any argument, it returns a value of −1.
This number is an identity element for ‘logand’ because its binary
representation consists entirely of ones. If ‘logand’ is passed
just one argument, it returns that argument.
; 30-bit binary values
(logand 14 13) ; 14 = 0000...001110
; 13 = 0000...001101
⇒ 12 ; 12 = 0000...001100
(logand 14 13 4) ; 14 = 0000...001110
; 13 = 0000...001101
; 4 = 0000...000100
⇒ 4 ; 4 = 0000...000100
(logand)
⇒ -1 ; -1 = 1111...111111
-- Function: logior &rest ints-or-markers
This function returns the bitwise inclusive OR of its arguments:
the Nth bit is 1 in the result if, and only if, the Nth bit is 1 in
at least one of the arguments. If there are no arguments, the
result is 0, which is an identity element for this operation. If
‘logior’ is passed just one argument, it returns that argument.
; 30-bit binary values
(logior 12 5) ; 12 = 0000...001100
; 5 = 0000...000101
⇒ 13 ; 13 = 0000...001101
(logior 12 5 7) ; 12 = 0000...001100
; 5 = 0000...000101
; 7 = 0000...000111
⇒ 15 ; 15 = 0000...001111
-- Function: logxor &rest ints-or-markers
This function returns the bitwise exclusive OR of its arguments:
the Nth bit is 1 in the result if, and only if, the Nth bit is 1 in
an odd number of the arguments. If there are no arguments, the
result is 0, which is an identity element for this operation. If
‘logxor’ is passed just one argument, it returns that argument.
; 30-bit binary values
(logxor 12 5) ; 12 = 0000...001100
; 5 = 0000...000101
⇒ 9 ; 9 = 0000...001001
(logxor 12 5 7) ; 12 = 0000...001100
; 5 = 0000...000101
; 7 = 0000...000111
⇒ 14 ; 14 = 0000...001110
-- Function: lognot integer
This function returns the bitwise complement of its argument: the
Nth bit is one in the result if, and only if, the Nth bit is zero
in INTEGER, and vice-versa.
(lognot 5)
⇒ -6
;; 5 = 0000...000101 (30 bits total)
;; becomes
;; -6 = 1111...111010 (30 bits total)
Info Catalog
elisp: Rounding Operations
elisp: Numbers
elisp: Math Functions