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

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

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

「十進法 → 二進法」変換。これも鉄則本公式解説とは異なる方法でやってみよう。

問題概要

二進法で表記された整数  N が与えられる。

整数  N の十進法表記を求めよ。

解法

たとえば、二進法で表された整数 1101 は、十進法では、次のように計算できる。

 1 \times 2^{3} + 1 \times 2^{2} + 0 \times 2^{1} + 1 \times 2^{0} = 8 + 4 + 1 = 13

このように「 2^{x} の値」を求めて、それらを足すことで求められる。この方法が鉄則本公式解説に書いてある。

もう一つの方法

しかし、もう一つ有名な方法がある。それは、二進法で表された整数 1101 を、左から順に桁の値を見ていき、

  • 2 をかける
  • その桁の値を足す

を繰り返す方法だ。値  0 から出発して、次の表のような手続きで計算できる。

桁の値 2 をかける その桁の値を足す
1  0 \times 2 = 0  0 + 1 = 1
1  1 \times 2 = 2  2 + 1 = 3
0  3 \times 2 = 6  6 + 0 = 6
1  6 \times 2 = 12  12 + 1 = 13

このようにして、0 から出発して、最終的な値 13 が得られた。この手続きをそのまま実装することで AC が得られる。

解答例コード

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

int main() {
    string N;
    cin >> N;
    
    int res = 0;
    for (auto c : N) {
        res *= 2;  // 2 をかける
        res += c - '0';  // その桁の値を足す
    }
    cout << res << endl;
}