(lispref.info)Bitwise Operations


Next: Transcendental Functions Prev: Arithmetic Operations Up: Numbers

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.  If COUNT is negative, `lsh' shifts zeros into
     the most-significant bit, producing a positive result even if
     INTEGER1 is negative.  Contrast this with `ash', below.

     Thus, the decimal number 5 is the binary number 00000101.  Shifted
     once to the left, with a zero put in the one's place, the number
     becomes 00001010, decimal 10.

     Here are two examples of shifting the pattern of bits one place to
     the left.  Since the contents of the rightmost place has been
     moved one place to the left, a value has to be inserted into the
     rightmost place.  With `lsh', a zero is placed into the rightmost
     place.  (These examples 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.

     Note, however that functions do not check for overflow, and a
     returned value may be negative (and in any case, no more than a 24
     bit value) when an integer is sufficiently left shifted.

     For example, left shifting 8,388,607 produces -2:

          (lsh 8388607 1)          ; left shift
               => -2

     In binary, in the 24 bit implementation, the numbers looks like
     this:

          ;; Decimal 8,388,607
          0111 1111  1111 1111  1111 1111

     which becomes the following when left shifted:

          ;; Decimal -2
          1111 1111  1111 1111  1111 1110

     Shifting the 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 the pattern of bits 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 the pattern of bits one place
     to the right divides the value of the binary number by two,
     rounding downward.

 - 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 a one in the
     leftmost position, while `lsh' puts a zero in the leftmost
     position.

     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 1111  1111 1111  1111 1010
               =>
          1111 1111  1111 1111  1111 1101

     In contrast, shifting the pattern of bits one place to the right
     with `lsh' looks like this:

          (lsh -6 -1)
               => 8388605
          
          ;; Decimal -6
          ;; becomes decimal 8,388,605.
          
          1111 1111  1111 1111  1111 1010
               =>
          0111 1111  1111 1111  1111 1101

     In this case, the 1 in the leftmost position is shifted one place
     to the right, and a zero is shifted into the leftmost position.

     Here are other examples:

          ;               24-bit binary values
          
          (lsh 5 2)          ;   5  =  0000 0000  0000 0000  0000 0101
               => 20         ;  20  =  0000 0000  0000 0000  0001 0100

          (ash 5 2)
               => 20
          (lsh -5 2)         ;  -5  =  1111 1111  1111 1111  1111 1011
               => -20        ; -20  =  1111 1111  1111 1111  1110 1100
          (ash -5 2)
               => -20

          (lsh 5 -2)         ;   5  =  0000 0000  0000 0000  0000 0101
               => 1          ;   1  =  0000 0000  0000 0000  0000 0001

          (ash 5 -2)
               => 1

          (lsh -5 -2)        ;  -5  =  1111 1111  1111 1111  1111 1011
               => 4194302    ;         0011 1111  1111 1111  1111 1110

          (ash -5 -2)        ;  -5  =  1111 1111  1111 1111  1111 1011
               => -2         ;  -2  =  1111 1111  1111 1111  1111 1110

 - Function: logand &rest INTS-OR-MARKERS
     This function returns the "logical and" of the arguments: the Nth
     bit is set in the result if, and only if, the Nth bit is set in
     all the arguments.  ("Set" means that the value of the bit is 1
     rather than 0.)

     For example, using 4-bit binary numbers, the "logical and" of 13
     and 12 is 12: 1101 combined with 1100 produces 1100.

     In both the binary numbers, the leftmost two bits are set (i.e.,
     they are 1's), so the leftmost two bits of the returned value are
     set.  However, for the rightmost two bits, each is zero in at
     least one of the arguments, so the rightmost two bits of the
     returned value are 0's.

     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.

          ;                24-bit binary values
          
          (logand 14 13)     ; 14  =  0000 0000  0000 0000  0000 1110
                             ; 13  =  0000 0000  0000 0000  0000 1101
               => 12         ; 12  =  0000 0000  0000 0000  0000 1100

          (logand 14 13 4)   ; 14  =  0000 0000  0000 0000  0000 1110
                             ; 13  =  0000 0000  0000 0000  0000 1101
                             ;  4  =  0000 0000  0000 0000  0000 0100
               => 4          ;  4  =  0000 0000  0000 0000  0000 0100

          (logand)
               => -1         ; -1  =  1111 1111  1111 1111  1111 1111

 - Function: logior &rest INTS-OR-MARKERS
     This function returns the "inclusive or" of its arguments: the Nth
     bit is set in the result if, and only if, the Nth bit is set in at
     least one of the arguments.  If there are no arguments, the result
     is zero, which is an identity element for this operation.  If
     `logior' is passed just one argument, it returns that argument.

          ;               24-bit binary values
          
          (logior 12 5)      ; 12  =  0000 0000  0000 0000  0000 1100
                             ;  5  =  0000 0000  0000 0000  0000 0101
               => 13         ; 13  =  0000 0000  0000 0000  0000 1101

          (logior 12 5 7)    ; 12  =  0000 0000  0000 0000  0000 1100
                             ;  5  =  0000 0000  0000 0000  0000 0101
                             ;  7  =  0000 0000  0000 0000  0000 0111
               => 15         ; 15  =  0000 0000  0000 0000  0000 1111

 - Function: logxor &rest INTS-OR-MARKERS
     This function returns the "exclusive or" of its arguments: the Nth
     bit is set in the result if, and only if, the Nth bit is set in an
     odd number of the arguments.  If there are no arguments, the
     result is 0.  If `logxor' is passed just one argument, it returns
     that argument.

          ;               24-bit binary values
          
          (logxor 12 5)      ; 12  =  0000 0000  0000 0000  0000 1100
                             ;  5  =  0000 0000  0000 0000  0000 0101
               => 9          ;  9  =  0000 0000  0000 0000  0000 1001

          (logxor 12 5 7)    ; 12  =  0000 0000  0000 0000  0000 1100
                             ;  5  =  0000 0000  0000 0000  0000 0101
                             ;  7  =  0000 0000  0000 0000  0000 0111
               => 14         ; 14  =  0000 0000  0000 0000  0000 1110

 - Function: lognot INTEGER
     This function returns the logical 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.

          ;;  5  =  0000 0000  0000 0000  0000 0101
          ;; becomes
          ;; -6  =  1111 1111  1111 1111  1111 1010
          
          (lognot 5)
               => -6


automatically generated by info2www