ABC081B - Shift only 備忘録 Java

イントロ

最近AtCoderを始めてみたのですが、初心者向けの問題集AtCoder Beginners Selectionの中のABC081Bで早速躓いてしまいました。
自分なりに噛み砕いてなんとか理解することができたという備忘録です。

問題

回答（例）

Main.java

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int bit = 0;
		for (int i = 0;i < N; i++) {
			bit |= sc.nextInt();
		}
		System.out.println(Integer.numberOfTrailingZeros(bit));
	}
}

解説

いくつかの整数を同時に、いずれかの数が割り切れなくなるまで2で割るとき、何回割れるかを求める問題です。

整数が何回2で割れるか

算数も危うい筆者のような初心者への前提知識として、整数が2で何回割り切れるかは、2進数ので表したとき右側（末尾）に何個ゼロがあるかを見ることで分かります。

10進数	2進数
1	1
2	10
3	11
4	100
5	101
6	110
7	111
8	1000
9	1001
10	1010
11	1011
12	1100
13	1101
14	1110
15	1111
16	10000
︙	︙

ORビット演算( |= )

bit |= sc.nextInt();
入力された複数の整数に対して、最も2で割ることができる回数が小さい数についての答えを調べるため、末尾が1になるまでORビット演算を行っています。
ORビット演算ってなに？という方は以下を参考にしてください。

要約すると、2つのビット値が与えられたとき、少なくとも1つが1であれば結果は1に、両方が0であれば結果は0になるというものです。
例えば、5(101) と 6(110) にORビット演算を行うと結果は 7(111)になります。

4(100) と 6(110) にORビット演算を行うと 6(110) になり、int型の変数bitに代入されます。
ここで問題に戻りますが、

いくつかの整数を同時に、いずれかの数が割り切れなくなるまで2で割るとき、何回割れるかを求めてください

4 と 6 が入力された場合、
100 or 110 = 110
となり、末尾にゼロは1つのため、2で割り切れるのは1回となります。

出力

System.out.println(Integer.numberOfTrailingZeros(bit));
見たことのないメソッドが出てきて若干ビビりましたが、bitのバイナリ表現の末尾にあるゼロの数を数え、その結果を返すものです。

4 と 6 が入力された場合、
int型の変数 bit には、ORビット演算された 110 が代入されているため、末尾のゼロの数 1 が出力されます。

参考

AtCoderに登録したら解くべき精選過去問10をJavaで解いてみた