読者です 読者をやめる 読者になる 読者になる

sataniC++

C++、競プロ、数学などについて色々考えたりします。

進数変換

数学 数学-整数

目標

ある非負整数をn進数で表す。(n\geq2
また、n進数で表された非負整数を10進数で表す。

説明

前説明

以下、n進数で表された整数mm_{(n)}と表します。


まず、314159_{(10)}の各桁の数字について考えてみます。

314159_{(10)}の各数字314159は、
それぞれの値が300000100004000100509であることを表していて、これらの和が314159_{(10)}となっています。

これを式で表すと、次のようになります。
314159_{(10)} = 9+50+100+4000+10000+300000

右辺の各項を10の累乗を掛けた形に直すと、
314159_{(10)} = 9\cdot 10^0+5\cdot 10^1+1\cdot 10^2+4\cdot 10^3+1\cdot 10^4+3\cdot 10^5

このことから、右辺のある項がa\cdot 10^i(0\leq a <10)であるとき、aは右端の数字からi個離れた桁の数字であることがわかります。


つまり、一般にある非負整数m_{(10)}n進数表記(m\geq2)で表したとき、右端の数字からi個離れた桁の数字をa_i(0\leq a_i < m)とすると、m_{(10)}は次のように表すことが出来ます。
m_{(10)}=a_0 + a_1 n^1 + a_2 n^2 + a_3 n^3 + ... ・・・★

このことを元に、進数を変換することが出来ます。

ある非負整数m_{(10)}n進数で表す。(n\geq2

それでは、m_{(10)}n進数で表してみます。


★式を見ると、右辺の中で唯一a_0だけがnの倍数ではないことがわかります。
よって、m_{(10)}nで割った余りがa_0であることがわかりました。


このことを、「A=BQ+R」という書き方で表すと、次のようになります。
m_{(10)}=n(a_1 + a_2 n^1 + a_3 n^2 + ...)+a_0

この式をよーく見てみると、★式の右辺と同じような構造の式があるのがわかりますね。
(a_1 + a_2 n^1 + a_3 n^2 + ...)」の部分です。
つまり、この部分についても同様にnで割った余りを求めることで、今度はa_1がわかります。


よって、
a_0=m_{(10)}nで割った余り
a_1=m_{(10)}nで割った商」をnで割った余り
a_2=「「m_{(10)}nで割った商」をnで割った商」をnで割った余り
...

となることがわかりました。

n進数で表された非負整数m_{(n)}10進数で表す。(n\geq2

こちらは上記のものより簡単です。

今、前提よりm_{(n)}の各桁の数字a_iがわかっているので、あとは★式に代入すればOKです。

具体例

70_{(10)}3進数で表す

70_{(10)}3で割っていけば良いので、
 \displaystyle \begin{align}
70\div 3&=23\cdots 1\\
23\div 3&=7\cdots 2\\
7\div 3&=2\cdots 1\\
2\div 3&=0\cdots 2
\end{align}

よって、70_{(10)}=2121_{(3)}であることがわかりました。
(上から見て1212_{(3)}ではないことに注意!)


なお、紙に書いて計算するときは次のような書き方をすることが多いです。
3)70
3)23...1
3) 7...2
3) 2...1
  0...2

3210_{(4)}10進数で表す

★式に代入し、右辺を計算するだけです。
{ \displaystyle \begin{align}
3210_{(4)}&=0+1\cdot 4^1 + 2\cdot 4^2 + 3\cdot 4^3\\
&=1\cdot 4+2\cdot 16+3\cdot 64\\
&=4+32+192\\
&=228
\end{align}}

よって、3210_{(4)}=228_{(10)}であることがわかりました。

11001_{(2)}3進数で表す

この場合は、10進数に直してから3進数にします。

まず、11001_{(2)}10進数で表します。
{ \displaystyle \begin{align}
11001_{(2)}&=1+0\cdot 2^1 + 0\cdot 2^2 + 1\cdot 2^3+ 1\cdot 2^4\\
&=1+ 1\cdot 8+ 1\cdot 16\\
&=1+8+16\\
&=25
\end{align}}

よって、11001_{(2)}=25_{(10)}です。

次に、25_{(10)}3進数で表します。
 \displaystyle \begin{align}
25\div 3&=8\cdots 1\\
8\div 3&=2\cdots 2\\
2\div 3&=0\cdots 2
\end{align}

よって、25_{(10)}=221_{(3)}です。

以上より、11001_{(2)}=221_{(3)}であることがわかりました。

コード(C++

以上の計算をC++のコードにしてみました。表記の都合上、n進数のn2以上10以下の整数であるとしています。なお、細かい例外処理などは行っていないので、必要に応じて実装してください。

ある非負整数m_{(10)}n進数で表す

//要ヘッダ:cmath
long long int ConvBase10ToN(long long int m, int n){
    if(n<2 || n>10) return m;
    long long int result=0;
    int basePos=0;
    do{
        result += m%n * std::pow(10, basePos);
        m/=n;
        ++basePos;
    }while(m/n!=0 || m%n!=0);
    return result;
}

n進数で表された非負整数を10進数で表す。

//要ヘッダ:cmath
long long int ConvBaseNTo10(long long int m, int n){
    if(n<2 || n>10) return m;
    long long int result=0;
    int basePos=0;
    while(m!=0){
        result += m%10 * std::pow(n, basePos);
        m/=10;
        ++basePos;
    }
    return result;
}

from進数で表された非負整数をto進数で表す。

以上の関数を組み合わせることで、このような関数を作ることも出来ます。

long long int ConvBase(long long int m, int from, int to){
    return ConvBase10ToN(ConvBaseNTo10(m, from), to);
}

あとがき

順を追って書いていたらなんだか結構長くなってしまいました。
あまり張り切りすぎても書くのが面倒くさくなってしまうと思うので、自分の負担にならず、かつ説明したい所は説明の出来ているちょうどいい記事を作っていけるように心がけます。
また、質問や、何か間違いなどあればコメントを頂けると嬉しいです。