問題概要

整数 $N$ が与えられる。

$N$ を二進法表記したものについて、先頭を 0 埋めすることで 10 桁で答えよ。

解法：二進法とは

整数 $N$ を二進法で表したときの各桁の値が求められれば良い。これは実は「2 で割った余りを見る」「2 で割る」を繰り返すという方法がよく知られている。なお、この方法は、高校の「情報 I」や「数学 IA」でも扱われている。

たとえば、13 は二進法で表すと 1101 となる。なぜならば、

$13 = 2^{3} + 2^{2} + 2^{0}$

であるから、二進法で表したときに右から 0, 2, 3 桁目が 1 になるのだ。なお、上の問題についていえば、先頭を 0 埋めして 10 桁にするので、

"0000001101"

が答えとなる。

「十進法 → 二進法」変換の方法

さて、13 を二進法に変換するのは、次の図のような方法でできる。

コードにすると、次のように書ける。

int N = 13;
vector<int> res;
while (N > 0) {
    res.push_back(N % 2);
    N /= 2;
}

これを実行すると、

res = {1, 0, 1, 1}

となる。この res は、 $N = 13$ を二進法で表したとき値 (1101 です) の右から 0, 1, 2, 3 桁目の値を表していることに注意しよう。そのため、res = {1, 1, 0, 1} とはならないのだ。

これをサイズ 10 になるまで 0 を埋めて、右から順に出力すれば OK。

解答例コード

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

int main() {
    int N;
    cin >> N;
    
    vector<int> res;  // 右から 0 桁目から順に push
    while (N > 0) {
        res.push_back(N % 2);
        N /= 2;
    }
    
    // 10 桁になるまで 0 を埋める
    while (res.size() < 10) res.push_back(0);
    
    // 右から 9, 8, ..., 0 桁目の順に出力する
    for (int i = 9; i >= 0; --i) {
        cout << res[i];
    }
    cout << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

鉄則本 A04 - Binary Representation 1 (6Q, ★2)

問題概要

解法：二進法とは

「十進法 → 二進法」変換の方法

解答例コード