C++ 繰り返し二乗法のコードの疑問点

Question

前提

繰り返し二乗法について勉強しています。aのb乗の計算法についてのコードでわからないところがあります。下のコードで「if ((b & (1 << i)) != 0」の部分が機能しているのかがわかりません。
１<<iの部分は二進数で１０、１００、１０００と増えていくことはわかります。そこからｂとAND演算をして何がもとまっているのかがわかりません。
また、「{ Answer *= p; Answer %= m; }p *= p; p %= m;」ここの部分でなぜ分けて何がしたいのかがわかっていません。
誰かご教授お願いします。

実現したいこと

繰り返し二乗法の理解を深めたい

該当のソースコード

#include <iostream>
using namespace std;

long long modpow(long long a, long long b, long long m) {
	// 繰り返し二乗法（p は a^1, a^2, a^4, a^8, ... といった値をとる）
	long long p = a, Answer = 1;
	for (int i = 0; i < 30; i++) {
		if ((b & (1 << i)) != 0) { Answer *= p; Answer %= m; }
		p *= p; p %= m;
	}
	return Answer;
}

const long long mod = 1000000007;
long long a, b;

int main() {
	cin >> a >> b;
	cout << modpow(a, b, mod) << endl;
	return 0;
}

Answer 1

if ((b & (1 << i)) != 0)

b のiビット目が立っているかどうかの判定をしてます

Answer 2

途中に「p は a^1, a^2, a^4, a^8, ... といった値をとる」というコメントが付いていますが、これらの値をかけ合わせて目的の累乗を作っていきます。

そこからｂとAND演算をして何がもとまっているのかがわかりません。

いまのpを結果に掛け合わせるかどうか、を判定しています。例えば、b=10の場合、a^10をa^8*a^2のように分けて計算していきます。

Comments

[jaogjig]

何を求めているかはわかりました。ありがとうございます。そこで新たな疑問点が出ました。
for (int i = 0; i < 30; i++) {if ((b & (1 << i)) != 0) { Answer *= p; Answer %= m; }p *= p; p %= m;}の部分で「p *= p; p %= m;」を３０回ｐを２乗してその余りを出す必要性がわかりません。

[maisumakun]

最終的に得たい結果が余りなので、大きくなりすぎないように途中であまりを取っています。

30までなのは想定される引数の範囲かと思われます。

[jaogjig]

「大きくなりすぎないように途中であまりを取っています。」というのはどういう意味ですか

[maisumakun]

書いてのとおりです。

最後に1回だけあまりを取ろうとすると途中経過がlong longをはみ出す危険がありますので、途中で余りを取ってその危険をなくしています（最終的に得られる結果は同じです）。