問題
正の整数 n が与えられたとき、その2進数表現において隣接する 1 同士の最大距離を求めます。
距離とは、2つの 1 のビット位置の差を意味します。隣接する 1 が存在しない場合は 0 を返します。
解法
この問題は、整数 n の各ビットを右から順番に確認することで解くことができます。
まず、整数 n を右に1ビットずつシフトしながら、現在のビットが 1 かどうかを確認します。
1 が見つかった場合、その位置を記録します。
最初の 1 は位置のみ保存し、それ以降に 1 が見つかるたびに、現在の位置と前回の位置との差を計算し、最大値を更新します。
その後、現在の位置を前回の位置として更新します。
この処理を n が 0 になるまで繰り返すことで、隣接する 1 同士の最大距離を求めることができます。
ビット演算を直接使用することで、文字列変換を行わず効率的に処理できます。
- 時間計算量: O(log n)
- 空間計算量: O(1)
コード（Java）
class Solution {
public int binaryGap(int n) {
int max = 0;
int index = 0;
int prev = -1;
while (n > 0) {
if ((n & 1) == 1) {
if (prev != -1) {
max = Math.max(max, index - prev);
}
prev = index;
}
n >>= 1;
index++;
}
return max;
}
}
ポイント
• n & 1 を使用して現在のビットが 1 か確認
• n >>= 1 で次のビットへ移動
• 前回の 1 の位置を記録し、距離の最大値を更新
ビット演算を使用することで、シンプルかつ高速に解くことができます。