AtCoder ABC 068 B - Break Number (6Q, 灰色, 200 点)

この手のものは関数化するのがオススメ！

• 問題へのリンク

問題概要

正の整数 が与えられる。

以上 以下の整数のうち、2 で割れる回数が最大のものを求めよ（タイがないことが証明できる）。

制約

• 

考えたこと

全探索しよう！

具体的には、 について、「 を 2 で何回割れるか」を求めてあげて、それが最大となる を答えればよい。

ここで注意したいことは、次のようなコードを書いてはいけない！

int max_kaisuu = -1, res = -1;
for (int x = 1; x <= N; x++) {
    int kaisuu = 0;  // x を 2 で何回割れるか
    while (x % 2 == 0) {
        kaisuu++;
        x /= 2;
    }

    if (kaisuu > max_kaisuu) {
        max_kaisuu = kaisuu;
        res = x;
    }
}

このコードの何が不味いかわかるだろうか。for 文の中で、x の値を変更してしまっているのだ。これではおかしな挙動になってしまう。

このようなことを防ぐためには「 が 2 で何回割れるかを求める」部分を関数化するのがおすすめだ。すると、次のコードのように書ける。

コード

#include <bits/stdc++.h>
using namespace std;

// x が 2 で何回割れるかを求める
int calc(int x) {
    int res = 0;
    while (x % 2 == 0) {
        res++;
        x /= 2;
    }
    return res;
}

int main() {
    int N;
    cin >> N;

    int max_val = -1, res = -1;
    for (int x = 1; x <= N; x++) {
        int num = calc(x);  // x を 2 で割れる回数
        if (max_val < num) {
            max_val = num;
            res = x;
        }
    }
    cout << res << endl;
}