倭マン's BLOG

くだらない日々の日記書いてます。 たまにプログラミング関連の記事書いてます。 書いてます。

いまさら!? ビット演算 ~論理演算編~

昨今、若者のビット演算離れが叫ばれてる、かどうかは知りませんが、ちょっとビット演算で気になったことがあったので復習も兼ねてビット演算をあれこれ試してみました。 ビット演算の解説は世に山のようにありますが、実際自分であれこれ書いてみないとどうもシックリこないところがあるので、山に砂を積んでみました。

今回は Java で演算子が定義されている

  • 否定(ビット反転) ~
  • 論理積 &
  • 論理和 |
  • 排他的論理和 ^

を見ていきます。  二項演算子である &, |, ^ には、対応する代入演算子 &=, |=, ^= もあります。 説明の必要はないかと思いますが、例えば「a &= b」は「a = a & b」と同じになります*1

準備

まずは、以降のサンプルコードで使う定数やメソッドの定義をしておきましょう。 この記事では int 値のビットごとの論理演算を見ていきますが、int 値を2進数の文字列で表す際に0と1だと見にくいので、0の代わりにアンダーバー (_) を使うことにします。

まず、2進数の数値を表した文字列を int 値に変換する b(String) メソッドを定義しておきましょう(使い方は次節):

    /** ビット文字列を int 値に変換するメソッド。 0の代わりにアンダーバー (_) を使える。 */
    static int b(String s){
        return Integer.parseUnsignedInt(s.replaceAll("_", "0"), 2);
    }
  • ここでは Integer#parseUnsigindInt() を使っていますが、これは最上位のビット(符号ビット)も1, 0(_) で書けるようにするためです。

また、32ビット全てを書くとコードが見づらくなるので、基本的に下位8ビットのみを明示して上位24ビットは全て0もしくは1となっている定数を使うことにします。

    static final String ___ = "________"+"________"+"________";  // 24個の0
    static final String lll = ___.replaceAll("_", "1");          // 24個の1

変数名の「lll」はアルファベットのエル3つです。 「___」は別になくてもいいんですが、負の数を扱うときに「lll」がいるので、その対比で用意しています。

最後の準備として、下位5ビットのみが1の定数を定義しておきましょう:

    static final int mask = b(___+"___11111");  // 下位5ビットのマスク (= 31)

これはビット演算と併せて使うとフィルタの役目をします。

整数値と負符号

では、前節で定義したメソッドや定数の使い方の確認も含めて、int 値とその二進数表現を見ていきましょう。 ついでに負の数や負符号についても確認しておきます.

まずは前節で定義した b() メソッドと定数「__」, 「lll」の使い方:

// b() メソッドで2進数表現(_ は0と同じ)を int 値に変換する
int x = b("1_11_1_");  // == 1011010
assert( x == 90 );

// 32ビットを全指定
int y = b(___+"_1_11_1_");  // 「___」は0が24個
assert( y == 90);

int z = b(lll+"1_1__11_");  // 「lll」は1が24個
assert( z == -90 );

// その他、いくつかの値
assert( b(___+"________") == 0 );  // 全てのビットが0なら値は0
assert( b(___+"_______1") == 1 );
assert( b("_1111111"+lll) == Integer.MAX_VALUE );  // == 2^31-1

assert( b(lll+"11111111") == -1 );  // 全てのビットが1なら値は-1
assert( b("1_______"+___) == Integer.MIN_VALUE );  // == -2^31
  • Java では int 値は32ビットで表され、そのとりうる値は  { -2^{31} } 以上  { 2^{31}-1 } 以下です。 int 値の最大値と最小値は、それぞれ Integer.MAX_VALUE, Integer.MIN_VALUE として Integer クラスに定義されています

最上位のビットは符号を表し(符号ビット)、0ならその数は正もしくは0、1ならその数は負となります。 符号ビットを0から1に変えれば、値は  { 2^{31} } を引いたものになります。 たとえば

  • 000...0 (= 0) → 100...0 (=  { -2^{31} })
  • 011...1 (=  { 2^{31}-1 }) → 111...1 (= -1)

負符号
負符号はビット演算には含まないと思いますが、後で少し使うのでビットレベルでどういう変換になっているのか見ておきましょう。

正の数に負符号をつけると、全ビットを反転して1を加えた負の数になります。 逆に負の数に負符号をつけると、1を引いて全ビットを反転した正の数になります。

int x = b(___+"_1_11_1_");
int y = b(lll+"1_1__11_");
assert( -x == y );
assert( -y == x );

// 1と-1
int  one = b(___+"_______1");
int _one = b(lll+"11111111");  // == -1
assert( -one == _one);
assert( -_one == one);

// Integer.MAX_VALUE (== 2^31-1)
int  max = b("0"+lll+"1111111");
int _max = b("1"+___+"______1");
assert( -max == _max);
assert( -_max == max);

// 0 と Integer.MIN_VALUE
assert( -0 == 0);
System.out.println( -Integer.MIN_VALUE );

「-0」は0、「-Integer.MIN_VALUE」は正しい値を返しません。

マスク
下位 p ビットのみが1の int 値は、論理演算と併せて使うと、その p ビット(もしくはそれ以外のビット)のフィルタとして使えます。 一般に下位 p ビットのマスクの値は  { 2^p - 1 } です。 いくつかの p の値については

  • p = 0 の場合は0
  • p = 31 の場合は Integer.MAX_VALUE
  • p = 32 の場合は -1

となっています(p = 0, 32 の場合をマスクというのか分かりませんが):

// 「準備」で定義した mask フィールド
assert( mask == b(___+"___11111") );
assert( mask == 31 );  // == 2^5-1

p の値によっては「0xFF」(=255, 8ビットのフィルタ)のように16進数のリテラルで初期化することが多いようです。

否定 NOT (~)

では Java に定義されている論理演算をするビット演算子を見ていきましょう。 まずは否定 (NOT) もしくはビット反転の「~」。 これは負符号のように前置演算子で、各ビットを反転します:

int x = b(___+"_1_11_1_");  //  90
int y = b(lll+"1_1__1_1");  // -91

assert( ~x == y );
assert( ~90 == -91 );

assert( ~y == x );
assert( ~-89 == 90 )

// いくつかの値
assert(  ~0 == -1 );
assert( ~-1 ==  0 );
assert( ~Integer.MAX_VALUE == Integer.MIN_VALUE);
assert( ~Integer.MIN_VALUE == Integer.MAX_VALUE);

ビット反転は符号反転と値が1だけズレるので注意。 ビット反転と符号反転は以下のように関係しています(数学では否定は前に  { \neg } を付けて表すので、ここでもそうします。 まぁ  { \TeX } でのフォントのためですけど):

  { \displaystyle\begin{align*}
  -x =
    \begin{cases}
      \neg x+1 & (0 < x < 2^{31}) \\
      x & (x = 0) \\
      \neg (x-1) & (-2^{31} < x < 0)
    \end{cases}
\end{align*}}

ビット反転は負符号と同様、2度施すと元に戻ります:

// 任意の int 値 x について
assert( ~~x == x );

下位 p ビットが1のマスクにビット反転を施すと、上位 (32-p) ビットが1のマスクになります:

// 準備で定義した mask (下位5ビットのマスク)
assert(  mask == b(___+"___11111") );
assert( ~mask == b(lll+"111_____") );

論理積 AND (&)

次は二項演算子の論理積 (&)。 1ビットの真理値表は以下で与えられます:

AND 0 1
0 0 0
1 0 1

int 値に対する & 演算子はビットごとの論理積を計算します。 以下のコードでは、x と y の論理和の結果が z となります。 縦にビットをそろえて、それぞれのビットごとの論理積がどのような結果になるかが簡単に見られるようにしています(これ以降のコードでも同じ):

int x = b(___+"_1_11_1_");
int y = b(___+"___1__11");
int z = b(___+"___1__1_");  // == x & y
assert( (x & y) == z );

また、論理積は可換かつ結合的です:

// 任意の int 値 x, y, z に対して
assert( (x & y) == (y & x) );
assert( ((x & y) & z) == (x & (y & z)) );

これ以上に知っておかなければならない性質は特にないと思いますが、いくつかの特別な場合を見ていきましょう。

自身との AND
自身との論理積は常に自分自身です:

// 自身との AND
int x = b(___+"_1_11_1_");
int y = b(___+"_1_11_1_");   // == x
int z = b(___+"_1_11_1_");  // == x & y
assert( (x & y) == z );

// つまり
assert( (x & x) == x );

(0, 0) のペアもしくは (1, 1) のペアしかないので当然ですね。 逆に、自身の否定(ビット反転)との論理積は常に0となります:

// 自身の否定との AND
int x = b(___+"_1_11_1_");
int y = b(lll+"1_1__1_1");  // == ~x
int z = b(___+"________");  // == x & y
assert( (x & y) == z );

// つまり
assert( (x & ~x) == 0 );

1と0が逆転してるので、論理積をとると常に0になりますからね。 さて、ちょっと変わった性質として、自身の符号反転(負符号をつけたもの)と論理積をとると、もとの int 値で最下位のビットだけが1となった int 値を返します:

// 自身の符号反転との AND
int x1 = b(___+"_1_11_1_");
int y1 = b(lll+"1_1__11_");  // == -x1
int z1 = b(___+"______1_");  // == x & y:x1 の最下位のビットのみが1
assert( (x1 & y1) == z1 );

int x2 = b(___+"_1_11___");
int y2 = b(lll+"1_1_1___");  // == -x2
int z2 = b(___+"____1___");  // == x & y:x2 の最下位のビットのみが1
assert( (x2 & y2) == z2 );

ちなみに、 Integer#lowestOneBit() メソッドはこの結果と同じく、引数の最下位のビットのみが1の int 値を返します:

assert( (x & -x) == Integer.lowestOneBit(x) );

マスクとの AND
準備の箇所で定義した mask は、論理積と一緒に使うとフィルタとして機能します:

// マスクとの AND
int x = b(___+"_1_11_1_");
int y = b(___+"___11111");  // == mask
int z = b(___+"___11_1_");  // == x & y
assert( (x & y) == z );

// 特別な場合
assert( (x &  0) == 0 );  // 0 は下位0ビットのマスク?
assert( (x & -1) == x );  // -1 は下位32 ビットのマスク?

下位 p ビットのマスクと論理積をとると、下位 p ビットだけをそのまま取り出し、上位 (32-p) ビットは全て 0 になります。

ちょっとどうでもいい話ですが、int 値 x と下位 p ビットのマスクの論理積をとると、結果は  { x\,\,\textrm{mod}\,\,2^p } となります。

/**
   * 剰余演算子の % ではなく、数学の mod での剰余。
   * 除数である第2引数 m は正でなくてはならず、結果は [0, m) の範囲の int 値となる。
   */
static int mod(int n, int m){
    if(n >= 0){
        return n % m;
    }else{
        int r = n % m;
        if(r == 0) return 0;
        else       return r + m;
    }
}

assert( (x & mask) == mod(x, mask+1) );  // mask (== 31) は下位5ビットのマスク

これは上位ビットの切り捨てと思えば正の int 値に対しては簡単に分かりますが、負の int 値について成り立つのは自明ではないので少し補足しておきましょう。  { x } が負のとき、まず符号ビットの1だけを0に変えると、値は  { x + 2^{32} } になります。 これは正の数なので上記の結果が使えて、残りの p ビットより上位のビットも0にすると  { x + 2^{32} \,\,\textrm{mod}\,\,2^p \equiv x   \,\,\textrm{mod}\,\,2^p } となって、正の数の場合と同じ結果になります。

マスクの否定(ビット反転)との論理積は、先ほどと逆に、上位 (32-p) ビットのみを取り出すフィルタとして機能します:

// マスクの否定との AND
int x = b(___+"_1_11_1_");
int y = b(lll+"111_____");  // == ~mask
int z = b(___+"_1______");  // == x & y
assert( (x & y) == z );

// 上で定義した mod() メソッドを使うと以下のようにも書ける
assert( (x & ~mask) == (x - mod(x,mask+1)) );

マスクとそのビット反転がそれぞれ下位 p ビットと上位 (32-p) ビットを抜き出すフィルタの役割をすることを念頭におくと、以下のような恒等式が成り立つことがわかります:

// 任意の int 値 x について
assert( ((x & ~mask) & (x & mask)) == 0 );
assert( ((x & ~mask) | (x & mask)) == x );
assert( ((x & ~mask) ^ (x & mask)) == x );

後でみる論理和、排他的論理和も入っちゃってますが。 mask は「準備」の箇所で定義した下位5ビットのマスクでなくてもかまいません*2

論理和 OR (|)

次は論理和の OR (|)。 1ビットでの真理値表は以下のようになってます:

OR 0 1
0 0 1
1 1 1

int 値同士の論理和も、論理積と同じくビットごとの論理和として計算されます:

int x = b(___+"_1_11_1_");
int y = b(___+"___1__11");
int z = b(___+"_1_11_11");   // == x | y
assert( (x | y) == z );

論理和も可換で結合的です:

// 任意の int 値 x, y, z に対して
assert( (x | y) == (y | x) );
assert( ((x | y) | z) == (x | (y | z)) );

また、いくつかの特別な値について計算していきましょう。

自身との OR
自身との論理和は、論理積と同じく自分自身と同じです:

// 自身との OR
int x = b(___+"_1_11_1_");
int y = b(___+"_1_11_1_");  // == x
int z = b(___+"_1_11_1_");   // == x | y
assert( (x | y) == z );

// つまり
assert( (x | x) == x );

自身の否定(ビット反転)との論理和は全てが1、つまり-1となります:

// 自身の否定との OR
int x = b(___+"_1_11_1_");
int y = b(lll+"1_1__1_1");  // == ~x
int z = b(lll+"11111111");   // == x | y
assert( (x | y) == z );

// つまり
assert( (x | ~x) == -1 );

論理積の場合と同じく、自身の符号反転(負符号をつけたもの)との論理和は最下位ビットに関連する値を返します:

// 自身の符号反転との OR
int x1 = b(___+"_1_11_1_");
int y1 = b(lll+"1_1__11_");  // == -x
int z1 = b(lll+"1111111_");   // == x | y:x1 の最下位のビットより下のビットのみが0
assert( (x1 | y1) == z1 );

int x2 = b(___+"_1_11___");
int y2 = b(lll+"1_1_1___");  // == -x2
int z2 = b(lll+"11111___");   // == x | y:x2 の最下位のビットより下のビットのみが0
assert( (x2 | y2) == z2 );

// 任意の int 値 x に対して
assert( (x | -x) == -Integer.lowestOneBit(x) );

自身と符号反転との論理和は、最下位のビットより下のビットのみが0で、最下位ビット以上のビットが1の int 値が返されます。 これは -Integer.lowestOneBit() に等しい値です。

マスクとの OR
次はマスクとの論理和。 論理積が0で切り捨てたのに対して、論理和は1で埋めるフィルタのような感じです。 切り捨てる場所と埋める場所が逆というのもありますが。 下位 p ビットのマスクとの論理和は、下位 p ビットを1で埋めて、上位 (32-p) ビットをそのまま保持します:

// マスクとの OR
int x = b(___+"_1_11_1_");
int y = b(___+"___11111");  // == mask
int z = b(___+"_1_11111");   // == x | y
assert( (x | y) == z );

// つまり
assert( (x | mask) == ((x & ~mask) | mask) );

// いくつかの特別な場合
assert( (x |  0) == x );
assert( (x | -1) == -1 );

マスクの否定(ビット反転)は、逆に上位 (32-p) ビットを1で埋めて、下位 p ビットをそのままにします:

// マスクの否定との OR
int x = b(___+"_1_11_1_");
int y = b(lll+"111_____");  // == ~mask
int z = b(lll+"11111_1_");   // == x | y
assert( (x | y) == z );

// つまり
assert( (x | ~mask) == (~mask | x & mask) );

論理積のときと同じように、任意の x と任意のマスク*3 mask に対して mask, ~mask とそれぞれ論理和をとったものに以下のような関係があります:

// 任意の int 値 x に対して
assert( ((x | ~mask) & (x | mask)) ==  x );
assert( ((x | ~mask) | (x | mask)) == -1 );
assert( ((x | ~mask) ^ (x | mask)) == ~x );

排他的論理和 XOR (^)

さて、最後は排他的論理和の XOR (^)。 真理値表は以下のようになっています:

XOR 0 1
0 0 1
1 1 0

名前の通り OR に似ていますが、両方1のときに0となります。 これは、2進数の足し算で 1+1 = 10 の結果の繰り上がり分を捨てるイメージですね。  { \textrm{mod}\,\,2 } の計算と言ってもいいでしょう。  排他的論理和の結果は、2値が同じなら0、異なるなら1とも言えます。

int 値同士の排他的論理和は、やはりビットごとの排他的論理和を行うだけです:

int x = b("_1_11_1_");
int y = b("___1__11");
int z = b("_1__1__1");   // == x ^ y
assert( (x ^ y) == z );

排他的論理和も可換で結合的です。 結合性は一見成り立っているかどうかが分かりにくいかも知れませんが(自分だけ?)、上記の2進数の和であることを思い起こせば納得がいくかと思います:

// 任意の int 値 x, y, z に対して
assert( (x ^ y) == (y ^ x) );
assert( ((x ^ y) ^ z) == (x ^ (y ^ z)) );

自身との XOR
排他的論理和は2値が同じなら0となるので、自身との排他的論理和は常に0となります:

// 自身との XOR
int x = b(___+"_1_11_1_");
int y = b(___+"_1_11_1_");  // == x
int z = b(___+"________");   // == x ^ y
assert( (x ^ y) == z );

// つまり
assert( (x ^ x) == 0 );

逆に、自身の否定(ビット反転)との排他的論理和は全ビットが1となります:

// 自身の否定との XOR
int x = b(___+"_1_11_1_");
int y = b(lll+"1_1__1_1");  // == ~x
int z = b(lll+"11111111");   // == x ^ y
assert( (x ^ y) == z );

// つまり
assert( (x ^ ~x) == -1 );

自身の符号反転との排他的論理和は、最下位以下のビットが0となり、最下位より上のビットが1となります:

// 自身の符号反転との XOR
int x = b(___+"_1_11_1_");
int y = b(lll+"1_1__11_");  // == -x
int z = b((lll+"111111__");  // == x ^ y
assert( (x ^ y) == z );

// つまり
assert( (x ^ -x) == (x | -x) << 1 );  // (x | -x) の結果を右へ1ビットずつずらしたもの

最後の行でビットシフトを行う << 演算子を使ってますが、これは次回に(別に難しくないけど)。 この結果は「(x | -x) - (x & -x)」とも書けますが、まぁ大した意味はなさそうです。

マスクとの XOR
次はマスクとの排他的論理和。 これは論理積や論理和の場合とちょっと違って「一部分を反転し、それ以外の部分をそのままにする」というフィルタになります:

// マスクとの XOR
int x = b(___+"_1_11_1_");
int y = b(___+"___11111");  // == mask
int z = b(___+"_1___1_1");  // == x ^ y
assert( (x ^ y) == z );

下位5ビットのマスクと排他的論理和をとると、下位5ビットは反転され、上位27ビットはそのままになっています。 ちょっと分かりにくいかも知れませんが、常に以下が満たされます:

// 任意の int 値 x に対して
assert( (x ^ mask) == ((x & ~mask) | (~x & mask)) );

mask が下位 p ビットのマスクとすると、「x & ~mask」は上位 (32-p) ビットをそのまま、下位 p ビットを0 にします。 また、「~x & mask」は x の反転に関して、下位 p ビットをそのまま、上位 (32-p) ビットを0にします。 これらの論理和をとると、上位 (32-p) ビットはそのまま、下位 p ビットは反転する、という結果になります。

ちなみに、特別なマスク?の場合の値は以下のようになります:

// 特別な場合
assert( (x ^ 0) == x );
assert( (x ^ -1) == ~x );

マスクの否定(ビット反転)との排他的論理和は、先ほどの逆で、上位 (32-p) ビットが反転、下位 p ビットがそのままとなります:

// マスクの否定との XOR
int x = b(___+"_1_11_1_");
int y = b(lll+"111_____");  // == ~mask
int z = b(lll+"1_111_1_");  // == x ^ y
assert( (x ^ y) == z );

// つまり
assert( (x ^ ~mask) == ((~x & ~mask) | (x & mask)) );

排他的論理和についても以下のような恒等式が成り立ちます:

// 任意の int 値 x, y, z に対して
assert( ((x ^ ~mask) & (x ^ mask)) ==  0 );
assert( ((x ^ ~mask) | (x ^ mask)) == -1 );
assert( ((x ^ ~mask) ^ (x ^ mask)) == -1 );

次回はこの続きでビットシフト演算子をやる予定。

【追記】

  • 負の数に対してマスクと論理積をとったときにも結果が mod を使って書けることの説明を追記しました。
  • 最初のあたりに代入演算子の箇所を追記しました。

Javaによる関数型プログラミング ―Java 8ラムダ式とStream

Javaによる関数型プログラミング ―Java 8ラムダ式とStream

  • 作者: Venkat Subramaniam,株式会社プログラミングシステム社
  • 出版社/メーカー: オライリージャパン
  • 発売日: 2014/10/24
  • メディア: 単行本(ソフトカバー)
  • この商品を含むブログ (3件) を見る

*1:int 値、long 値以外の整数型に関しては微妙に違いますが、同じように使えます。

*2:というか、よく考えるとマスクでなく任意の int 値でも成り立ちそうですが。

*3:マスクでなく、任意の int 値について成り立ちますかね。