シフト演算子の使い方

Question

AtCoderという競技プログラミングのサイトで基礎的な問題を解いていて、他の方の回答にシフト演算子を使ったものを見つけました。

1つ目のコードが私のもので、他の多くの回答と比べてもごく一般的だと思います。
2つ目が気になっているものです。
どうして2乗して右に2桁シフトすると1つ目と同じ結果になるのかがまるで理解できません。
">>"で1/4になるのは分かるのですが、kが奇数のとき、k^2 / 4は小数となるはずなのに、このコードが問題なく整数の答えを返すのはなぜでしょうか?

シフト演算子やビット演算という言葉をここ数十分で知ったので根本的な誤解があるかもしれませんが、よろしくお願いします。

A - Pair

1以上K以下の正の整数から、偶数と奇数ひとつずつの組を選ぶ方法の個数を求めてください。
なお、選ぶ順番は考慮しません。

k = int(input())
print((k // 2) * ((k + 1) // 2))

print(int(input()) ** 2 >> 2)

Answer 1

">>"で1/4になるのは分かるのですが、kが奇数のとき、k^2 / 4は小数となるはずなのに、

python3において >>などのビット演算は、整数を引数にとり、演算結果も整数です。

Python3 - 6.8. シフト演算 (shifting operation)

ビット演算ですので、2進数表記のビット単位で考えないと動きが分かりづらいと思います。2ビットシフトすると1/4になるのは結果的にそうなる場合があるというだけで、実際は右シフトするごとに最下位ビットは消えます。ですので奇数の場合でも 3 --> 1.5 --> 0.75 などとなるわけではありません。

下に、整数 7 を1ビットずつ右シフトする例を示してみます。

$ python3
Python 3.6.8 (default, Feb 15 2019, 01:54:23)
[GCC 7.4.0] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> k = 7
>>> print(k, bin(k))
7 0b111
>>> print(k >> 0, bin(k >> 0))
7 0b111
>>> print(k >> 1, bin(k >> 1))
3 0b11
>>> print(k >> 2, bin(k >> 2))
1 0b1
>>> print(k >> 3, bin(k >> 3))
0 0b0
>>> print(k >> 4, bin(k >> 4))
0 0b0
>>>

---

追記しました：2019/04/21 10:18

k ** 2 >> 2でk以下の奇数の数 * 偶数の数を求められる訳が依然として分かりません。
もしよろしければ、そちらについても解説していただけないでしょうか?

とコメントをいただいたので解法の意味するところまで考えていましたが、投稿直前に解決してしまいましたね。KSwordOfHasteさんの回答は私にとっても参考になったのですが、せっかく書いたので、考察のひとつとして追記しておきます。（間違いなどあればご指摘大歓迎です）

k ** 2 >> 2 は、解法として (k // 2) * ((k + 1) // 2) とほぼ同じ意味合いを持っていると思います。冗長部分を削ぎ落としたショートカット(近道)と言って良いでしょうか。

k = 11として、python3での(k // 2) * ((k + 1) // 2)式を一般の数式に当てはめてみます。(整数での演算なので、小数点以下は切り捨てられますが)

(11 ÷ 2) × ((11 ＋ 1) ÷ 2) = 5 × 6 = 30

これは、11 × (11 ＋ 1) ÷ 2 ÷ 2 と変形できます。縮めれば 11 × 12 ÷ 4　です。答えは33になってしまいますが、考え方は同じように見えます。変形したために(11 ÷ 2)がなくなるので、小数部分が欠落せず、計算が合いませんがこれは仕方ありません。対して、k ** 2 >> 2 を一般の数式に当てはめて見てみると 11 × 11 ÷ 4 ＝ 30　です。前述の式とほぼ同じです。

。。。納得行きませんか？　そうですね。私もなんか釈然としませんでした。発想を変えて、k ** 2 >> 2 の式の意味するところを考えてみます。

ひとまず偶数奇数を考えず、kを二乗するのは、全組み合わせ数を求めるためのものとします。数が大きくなると面倒なので、k = 7とします。

まず、単純に全部の組み合わせ数を求めると、7 × 7 = 49 です。

問題の求めるところは奇数と偶数のペアですから、偶奇が同じぺアは除外します。ここで1/2 します。

各組み合わせにおいては(1, 2)と(2, 1)は同じですから、それらは除外します。つまり、ここで更に1/2します。

1/2 を2回するわけで、1/4 、つまり 右2ビットシフト >> です。k ** 2 >> 2 は この工程、(全組み合わせ数) ÷ 4 を表現したプログラミングと見ることができると思います。

AtCoderの該当の回答者さんがどういう思考でこの式に辿りついたか私には伺い知れませんが、なるほど、と思いました。実は私もこのAtCoder A問題を過去に解いたことがあったのでコードを見直してみたのですが、晒すには恥ずかしいほどに愚直な方法で解いていました。

以上、ご参考までとなります。

Comments

[退会済みユーザー]

teratailでの質問前に公式ドキュメントを読んだのですがよく分からず、一般のウェブサイトの解説を流し見したために1/4になると勘違いしていました。
dodox86さんの解答を見て、自分でもbin()で色々な奇数の値を試してみました。
ですが、k ** 2 >> 2でk以下の奇数の数 * 偶数の数を求められる訳が依然として分かりません。
もしよろしければ、そちらについても解説していただけないでしょうか?

[退会済みユーザー]

丁寧な解説、本当にありがとうございます!
偶奇の数学的な解説を理解はしたものの、狐につつまれたような気分でいたのですが、dodox86さんの図を使った解説で腑に落ちました。

Answer 2

kが奇数なら

・k // 2 == (k - 1) / 2
・((k + 1) // 2) == (k + 1) / 2
問題の答えは((k - 1) * (k + 1)) / 4 == (k ** 2 - 1) / 4 == k ** 2 // 2 / 2(※)

※: kが奇数なのでk ** 2も奇数だから
(k ** 2 - 1) / 4
はk ** 2の下位1ビットを無視して4で除算することと同じと考えることができる

kが偶数なら

・k // 2 == k / 2
・((k + 1) // 2) == k / 2
・問題の答えは(k / 2) * (k / 2) == k ** 2 / 4

つまりkの偶奇によらず問題の答えはk ** 2をあまりを無視して4で割ることと同じ...つまり

k ** 2 >> 2

ということになるわけです。

---

上記の奇数のときの論理が不十分だったので訂正します：

k(奇数)より1小さい偶数をeとすると
k ** 2 == (e + 1) ** 2 == e ** 2 + 2 * e + 1
eは偶数なのでe ** 2は偶数、2 * eも偶数。よってe ** 2 + e * 2は必ず4の倍数になる。
つまりkが奇数の時、k ** 2のLSB(下位1ビット)は必ず1で、LSBの一つ上の桁のビットは必ず0になる。
故に(k ** 2 - 1) / 4 == k ** 2 >> 2と同じとなる

Comments

[退会済みユーザー]

なるほど、簡単な数学とビット表記の組み合わせで理解できるものだったんですね。
使いこなせるように、自分でも調べてみます。
ありがとうございました。