TL;DR
競技プログラミングで、ある整数を2で何回割れるかを求める必要があった。
ABC081B - Shift only
ベタに2で割り切れなくなるまでwhile文で回して求めていたけれど、もう少し、洗練されたやり方がないかを考えた。
求めたいこと
ある整数nは、2で何回割れるか？
| 整数 | 割り算 | 答え |
|---|---|---|
| 2 | 2÷2=1 | 1回 |
| 8 | 8÷2=4 4÷2=2 2÷2=1 |
3回 |
| 100 | 100÷2=50 50÷2=25 |
2回 |
ベタな数え方
while文を使って、2で割り切れなくなるまで割り続ける
num = int(input())
cnt = 0
while num % 2 == 0:
num //= 2
cnt += 1
print(cnt)
多少は数学的かも知れない求め方
2進数に変換して、右から検索して、最初に1が出現するまでの0の個数を数えればそれが答えであることに気づいた
| 10進数 | 2進数 | 求め方 | 答え |
|---|---|---|---|
| 2 | 10 | 1[0] | 1 |
| 8 | 1000 | 1[000] | 3 |
| 100 | 1100100 | 11001[00] | 2 |
これをコードにすると以下の通り
num = int(input())
print(format(num, 'b')[::-1].find('1'))
- 与えられた数字を2進数に変換する
-
format(num, 'b')プレフィックスなしの2進数文字列
参考リンク：pythonで2進数を表す - Qiita
-
- 右から1が出現するまで0の個数を数える
-
[::-1]：文字列を逆順にする
参考リンク：Python 文字列反転 - Qiita -
find('1')：最初に1が出現する箇所を見つける
-
注意事項
- 所詮は、数学苦手なおじさん(42歳東京都)が背伸びできる範囲内で考えた解法
- よりエレガントな求め方があれば、教えて下さい
蛇足：昨日時点のウルトラ糞コード
提出 #7088898 - AtCoder Beginners Selection
俺は何がしたかったんだろう・・・