質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.82%

シフト演算子の使い方

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,269

solzard

score 102

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)
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

+4

">>"で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) × ((111) ÷ 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 です。
image

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

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

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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/04/21 03:05

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

    キャンセル

  • 2019/04/21 11:02

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

    キャンセル

checkベストアンサー

+1

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と同じとなる

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/04/21 09:58

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.82%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る