次: , 前: Rounding Operations, 上: Numbers


3.8 整数のビット演算

計算機内部では、整数は2進数、つまり、 ビット(bit、各桁は0か1)列で表現されます。 ビット演算は、そのようなビット列の各ビットごとに作用します。 たとえば、シフト(shifting)は、ビット列を全体として左や右に 1桁以上移動して、その『移動後の』パターンを結果とします。

Emacs Lispにおけるビット演算は整数に限ります。

— 機能: lsh integer1 count

論理シフト(logical shift)の略からきているlshは、 integer1のビット列をcount桁左へ、 あるいは、countが負ならば右へずらし、空いたビットには0を詰める。 countが負であれば、lshは最左(最上位)ビットに0を詰め、 integer1が負であっても結果は正になる。 これと対照的なのが下のash

lshの例を2つ示す。 ビットパターンを1桁左へずらす。 ビットパターンの上位ビットはすべて0なので下位8ビットだけを示す。

          (lsh 5 1)
               => 10
          
          ;; 10進数5は、 10進数10になる
          00000101 => 00001010
          
          (lsh 7 1)
               => 14
          
          ;; 10進数7は、10進数14になる
          00000111 => 00001110
     

例からわかるように、ビットパターンを1桁左へずらすと、 もとの数値の2倍の数になる。

ビットパターンを2桁左へずらすと、(8ビット長の2進数では)つぎのようになる。

          (lsh 3 2)
               => 12
          
          ;; 10進数3は、10進数12になる
          00000011 => 00001100
     

一方、右へずらすとつぎのようになる。

          (lsh 6 -1)
               => 3
          
          ;; 10進数6は、10進数3になる
          00000110 => 00000011
          
          (lsh 5 -1)
               => 2
          
          ;; 10進数5は、10進数2になる
          00000101 => 00000010
     

例からわかるように、ビットパターンを1桁右へずらすと、 正の整数の数を2で除して切り下げる。

Emacs Lispのすべての算術関数と同様に、 関数lshは桁溢れ(オーバフロー)を検査しないので、 左へずらすと上位ビットを捨てさり数の符号を変えてしまうことがある。 たとえば、28ビット長の計算機では、 134,217,727を左へずらすと−2になる。

          
          (lsh 134217727 1)          ; 左シフト
               => -2
     

28ビット長の実装の2進数では、引数はつぎのようになっている。

          
          ;; 10進数134,217,727
          0111  1111 1111  1111 1111  1111 1111
     

これを左へずらすと、つぎのようになる

          
          ;; 10進数−2
          1111  1111 1111  1111 1111  1111 1110
     
— 機能: ash integer1 count

ash算術シフト(arithmetic shift))は、 integer1のビットをcount桁左へ、あるいは、 countが負ならば右へずらす。

ashlshと同じ結果になるが、 integer1countの両者が負の場合を除く。 この場合、ashは左の空いたビットには1を入れるが、 lshはそのようなビットには0を入れる。

したがって、ashでビットパターンを1桁右へずらすとつぎのようになる。

          (ash -6 -1) => -3
          
          ;; 10進数−6は、10進数−3になる
          1111  1111 1111  1111 1111  1111 1010
               =>
          1111  1111 1111  1111 1111  1111 1101
     

対照的に、lshでビットパターンを1桁右へずらすとつぎのようになる。

          (lsh -6 -1) => 134217725
          
          ;; 10進数−6は、10進数134,217,725になる
          1111  1111 1111  1111 1111  1111 1010
               =>
          0111  1111 1111  1111 1111  1111 1101
     

他の例を以下にしめす。

          
                             ;               28ビット2進値
          
          (lsh 5 2)          ;   5  =  0000  0000 0000  0000 0000  0000 0101
               => 20         ;      =  0000  0000 0000  0000 0000  0001 0100
          (ash 5 2)
               => 20
          (lsh -5 2)         ;  -5  =  1111  1111 1111  1111 1111  1111 1011
               => -20        ;      =  1111  1111 1111  1111 1111  1110 1100
          (ash -5 2)
               => -20
          (lsh 5 -2)         ;   5  =  0000  0000 0000  0000 0000  0000 0101
               => 1          ;      =  0000  0000 0000  0000 0000  0000 0001
          (ash 5 -2)
               => 1
          (lsh -5 -2)        ;  -5  =  1111  1111 1111  1111 1111  1111 1011
               => 4194302    ;      =  0011  1111 1111  1111 1111  1111 1110
          (ash -5 -2)        ;  -5  =  1111  1111 1111  1111 1111  1111 1011
               => -2         ;      =  1111  1111 1111  1111 1111  1111 1110
     
— 機能: logand &rest ints-or-markers

この関数は引数の『論理積』を返す。 つまり、すべての引数のn番目のビットが1である場合に限り、 結果のn番目のビットも1になる。

たとえば、4ビットの2進数で考えると、 13と12の『論理積』は12になる。 つまり、1101に1100を組み合わせると1100になる。 どちらの2進数も最左の2ビットは1なので、戻り値の最左の2ビットも1になる。 しかし、最右の2ビットは、一方の引数ではそれぞれが0なので、 戻り値の最右の2ビットも0になる。

したがって、つぎのとおり。

          (logand 13 12)
               => 12
     

logandにまったく引数を指定しないと値−1を返す。 この数は2進表現ではすべて1だけなので、 logandの恒等元である。 logandに引数を1つだけ指定するとその引数を返す。

          
                             ;                28ビット2進値
          
          (logand 14 13)     ; 14  =  0000  0000 0000  0000 0000  0000 1110
                             ; 13  =  0000  0000 0000  0000 0000  0000 1101
               => 12         ; 12  =  0000  0000 0000  0000 0000  0000 1100
          
          (logand 14 13 4)   ; 14  =  0000  0000 0000  0000 0000  0000 1110
                             ; 13  =  0000  0000 0000  0000 0000  0000 1101
                             ;  4  =  0000  0000 0000  0000 0000  0000 0100
               => 4          ;  4  =  0000  0000 0000  0000 0000  0000 0100
          
          (logand)
               => -1         ; -1  =  1111  1111 1111  1111 1111  1111 1111
     
— 機能: logior &rest ints-or-markers

この関数は引数の『論理和』を返す。 つまり、少なくともどれか1つの引数のn番目のビットが1である場合に限り、 結果のn番目のビットも1になる。 引数を指定しないと0を返すが、これはこの演算の恒等元である。 logiorに引数を1つだけ指定するとその引数を返す。

          
                             ;                28ビット2進値
          
          (logior 12 5)      ; 12  =  0000  0000 0000  0000 0000  0000 1100
                             ;  5  =  0000  0000 0000  0000 0000  0000 0101
               => 13         ; 13  =  0000  0000 0000  0000 0000  0000 1101
          
          (logior 12 5 7)    ; 12  =  0000  0000 0000  0000 0000  0000 1100
                             ;  5  =  0000  0000 0000  0000 0000  0000 0101
                             ;  7  =  0000  0000 0000  0000 0000  0000 0111
               => 15         ; 15  =  0000  0000 0000  0000 0000  0000 1111
     
— 機能: logxor &rest ints-or-markers

この関数は引数の『排他的論理和』を返す。 つまり、引数のn番目のビットが1であるものが奇数個の場合に限り、 結果のn番目のビットも1になる。 引数を指定しないと0を返すが、これはこの演算の恒等元である。 logxorに引数を1つだけ指定するとその引数を返す。

          
                             ;               28ビット2進値
          
          (logxor 12 5)      ; 12  =  0000  0000 0000  0000 0000  0000 1100
                             ;  5  =  0000  0000 0000  0000 0000  0000 0101
               => 9          ;  9  =  0000  0000 0000  0000 0000  0000 1001
          
          (logxor 12 5 7)    ; 12  =  0000  0000 0000  0000 0000  0000 1100
                             ;  5  =  0000  0000 0000  0000 0000  0000 0101
                             ;  7  =  0000  0000 0000  0000 0000  0000 0111
               => 14         ; 14  =  0000  0000 0000  0000 0000  0000 1110
     
— 機能: lognot integer

この関数は引数の論理的な補数を返す。 つまり、integern番目のビットが0である場合に限り、 結果のn番目のビットは1になる。

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