はじめに
競技プログラミングなどでよく見かけるビット演算、シフト演算ですが、業務上なかなか利用しない、競技プログラミング向けの記事がC++、Ptythonばかりで、Javaでのビット演算、シフト演算を忘れてしまったときに困ったので備忘録として書きます。
Javaで競技プログラミングをしたい方、Javaを利用したプロジェクトでビット演算、シフト演算を利用したくなった方に読んでいただければ嬉しいです。
ビット演算
ビット演算子
簡単にビット演算子をおさらいしておきます。
| 記号 | 使用例 | 意味 |
|---|---|---|
| & | a & b | a と b の論理積(ビットAND) |
| | | a | b | a と b の論理和(ビットOR) |
| ^ | a^b | a と b の排他的論理和(ビットXOR) |
| ~ | ~a | a のビット反転(ビットNOT) |
具体例（ビット演算）
a = 1100, b = 0101 として具体例を見ていきましょう。
| 数式 | 4桁目 | 3桁目 | 2桁目 | 1桁目 |
|---|---|---|---|---|
| a | 1 | 1 | 0 | 0 |
| b | 0 | 1 | 0 | 1 |
| a & b | 0 | 1 | 0 | 0 |
| a | b | 1 | 1 | 0 | 1 |
| a ^ b | 1 | 0 | 0 | 1 |
| ~a | 0 | 0 | 1 | 1 |
上記の具体例の通り、
- 論理積では1がaとbの両方に出現している桁のみ 1 になります。
- 論理和では1がaとbどちらか一方に出現していれば 1 になります。
- 排他的論理和では1がaとbどちらか片方に出現している桁のみ 1 になります。
- ビット反転では 1 と 0 が入れ替わっています。
それでは、具体例をそれぞれサンプルコードを実行して見ていきましょう。
サンプルコードで確認
論理積(ビットAND)
public class Main {
public static void main(String[] args) {
int a = 12; // 2進数 : 1100
int b = 5; // 2進数 : 0101
System.out.println("論理積(ビットAND) ：" + Integer.toBinaryString(a & b));
}
}
実行した結果は下記の通りです。
論理積(ビットAND) ：100
Binary出力の場合、左側の0部分は桁数としての表示が省略されるため、今回だと論理積結果は「100」と表示されています。
論理和(ビットOR)
public class Main {
public static void main(String[] args) {
int a = 12; // 2進数 : 1100
int b = 5; // 2進数 : 0101
System.out.println("論理和(ビットOR)：" + Integer.toBinaryString(a | b));
}
}
実行した結果は下記の通りです。
論理和(ビットOR)：1101
排他的論理和(ビットXOR)
public class Main {
public static void main(String[] args) {
int a = 12; // 2進数 : 1100
int b = 5; // 2進数 : 0101
System.out.println("排他的論理和(ビットXOR)：" + Integer.toBinaryString(a ^ b));
}
}
実行した結果は下記の通りです。
排他的論理和(ビットXOR)：1001
ビット反転(ビットNOT)
public class Main {
public static void main(String[] args) {
int a = 12; // 2進数 : 1100
System.out.println("ビット反転(ビットNOT)：" + Integer.toBinaryString(~a));
}
}
実行した結果は下記の通りです。
ビット反転(ビットNOT)：11111111111111111111111111110011
int型は32bitで定義されているため、元々「12(十進数)」は「00000000000000000000000000001100」です。そのため今回だとビット反転した結果は「11111111111111111111111111110011」と表示されています。
シフト演算
シフト演算子
簡単にシフト演算子をおさらいしておきます。
| 記号 | 使用例 | 意味 |
|---|---|---|
| << | a << n | aを左へnビットシフト |
| >> | a >> n | aを右へnビットシフト(符号有り) |
| >>> | a >>> n | aを右へnビットシフト(符号無し) |
具体例（シフト演算）
a, n を列に記載してある具体例を用いてみていきましょう。
| 数式 | a = 12 , n = 1 | a = 12 , n = 2 | a = 13 , n = 1 | a = -8 , n = 1 |
|---|---|---|---|---|
| a << n | 24 | 48 | 26 | -16 |
| a >> n | 6 | 3 | 6 | -4 |
| a >>> n | 6 | 3 | 6 | 2147483644 |
ちょっとピンとこない方も多いかもしれませんね。
ここで、数字を十進数ではなく二進数に直してみましょう。
| 数式 | a = 1100 , n = 1 | a = 1100 , n = 2 | a = 1101 , n = 1 | a = 111111111111111111111111111111000 , n = 1 |
|---|---|---|---|---|
| a << n | 11000 | 110000 | 11010 | 11111111111111111111111111110000 |
| a >> n | 110 | 11 | 110 | 11111111111111111111111111111100 |
| a >>> n | 110 | 11 | 110 | 01111111111111111111111111111100 |
二進数にしてみたら分かりやすくなりました。
aの数字を n 桁だけ左もしくは右にずらすのが、シフト演算です。
>>と>>>の違いを見てみましょう。
>>は符号あり、>>>は符号なしでしたね。
符号ありのシフト演算は最上位の符号に従いずらします。（正の整数には見えない0が左に付いています。）
そのため、負の数のときは最上位の数字が1であるため、負の数のままになります。
しかし、>>>の演算では最上位が1であっても0であっても、
その数字がどちらであるにしても、左端から0を増やして、右端にある数字を削除する動きをします。
だから十進数では、2倍や1/2倍という風に数字が変化していきます。
それでは、具体例をそれぞれサンプルコードを実行して見ていきましょう。
サンプルコードで確認
aを左へnビットシフト
public class Main {
public static void main(String[] args) {
int a = −８; // 2進数 : 1111111111111111111111111111000
int n = 1;
System.out.println("十進数：" + (a << n));
System.out.println("二進数：" + Integer.toBinaryString(a << n));
}
}
実行した結果は下記の通りです。
十進数：-16
二進数：11111111111111111111111111110000
aを右へnビットシフト（符号あり）
public class Main {
public static void main(String[] args) {
int a = −８; // 2進数 : 1111111111111111111111111111000
int n = 1;
System.out.println("十進数：" + (a >> n));
System.out.println("二進数：" + Integer.toBinaryString(a >> n));
}
}
実行した結果は下記の通りです。
十進数：-4
二進数：11111111111111111111111111111100
aを右へnビットシフト（符号なし）
public class Main {
public static void main(String[] args) {
int a = −８; // 2進数 : 1111111111111111111111111111000
int n = 1;
System.out.println("十進数：" + (a >>> n));
System.out.println("二進数：" + Integer.toBinaryString(a >>> n));
}
}
実行した結果は下記の通りです。
十進数：2147483644
二進数：1111111111111111111111111111100
まとめ
実際に実行しながら手を動かすと理解が進むと思います。
Javaを普段利用している方は、サンプルコードをコピペして、色々と試してみてください。