３進数を１０進数に変換

質問

３進数や５進数のように２の階乗ではない任意の進数の文字列を、C言語のビットシフトを使って１０進数に変換するプログラムについて、質問させていただきます。
ビットシフトを使わないで、任意の進数の文字列を１０進数に変換する方法は分かっていますが、ビットシフトを使った方が非常に計算が高速で出来るので、ビットシフトを使いたいと思っています。

下記のプログラムは４進文字列を１０進整数に変換するものです。２進、８進文字列の場合は、シフトするビット数を１ビット、３ビット（つまり、ans <<= 1、ans <<= 3）にすれば計算することが可能です。しかし、３進数や５進数の場合、いろいろと考えたのですが、どのようにすれば良いのか分かりません。

下記のプログラムのようにビットシフトを使って３進数や５進数の文字列を１０進数に変換するには、どのように工夫すれば良いでしょうか？　どなたかご教授をお願いいたします。

#define STRING_NUM 2 /* 文字列の長さ */
int main(void)
{

int i;
int ans = 0; /* 10進数の整数 */
char buf[STRING_NUM]; /* 4進数の文字列 */

buf[0] = '3';
buf[1] = '1';

for ( i = 0 ; i < STRING_NUM; i++ ){
printf(" %c", buf[i]);
}
printf("\n");

for ( i = 0 ; i < STRING_NUM; i++ ){
if ( buf[i] == '0' ){
ans <<= 2; /* シフトするビット数 */
ans |= 0;
}
if ( buf[i] == '1' ){
ans <<= 2;
ans |= 1;
}
if ( buf[i] == '2' ){
ans <<= 2;
ans |= 2;
}
if ( buf[i] == '3' ){
ans <<= 2;
ans |= 3;
}
}

printf( "ans = %d\n", ans );
return 0;
}

回答No.6

kmee · ベストアンサー

この実行環境はなんでしょう?
コンパイラはなんでしょう?
・例えば、a*3は、内部では
(a << 1) + (a << 0)
a*5は
(a << 2) + (a << 0)
と計算されている可能性が高いです。

・CPU等の回路構成では、上のような乗算を回路で高速に演算できるようになっています。
ビットシフトを自分で書くより高速でしょう。

・コンパイラの種類や設定によってできるオブジェクトは変わりますが
乗算はCPUに専用命令があるなら、それを積極的に使おうとするでしょう。
プログラム中でシフト+加算で書いてあったら、乗算に置き換えてくれることはまず無いでしょう。

これが、8bitマイコン用、とかなら、自分でシフト使った方が早いかもしれませんが、PCに入っているようなものだったら、素直に乗算使った方が速いのではないでしょうか

お礼

引き続きの回答有り難うございます。
以前、ビットシフトの方が単なる掛け算をするより早いという話を聞いたことがあったので、ずっと今もそういういものだと信じ込んでいました。調べてみると、昔は確かにそうだったようですが、今はKmeeさんがご指摘の通り、大きな差はないようです。
ご指摘ありがとうございました。

回答No.5

nak777r

話の途中で送ってしまいましたが、

言いたい事は、ビットシフトしているから早いのではなく
指定した桁を指定した位置に置いてるだけ
指定した位置にを実現するのにビットシフトを使っているだけです

なので、３ビットやら５ビットやらはそもそも
指定した位置に置くだけではそもそも違う値なので
ビットシフトでどうにかなるものではないです

まぁ２つ一致しない２進数をさらなるビットシフトでどうにか
できるのなら話は別ですが、その法則を導き出す
なら、演算したほうが早いです。

お礼

引き続きの回答有り難うございます。
ビットシフトに意味を、もう１度しっかり理解したいと思います。

回答No.4

nak777r

4進数=2進数=10進数
000 = 00-00-00 = 0
001 = 00-00-01 = 1
002 = 00-00-10 = 2
003 = 00-00-11 = 3
010 = 00-01-00 = 4
011 = 00-01-01 = 5
012 = 00-01-10 = 6
013 = 00-01-11 = 7
020 = 00-10-00 = 8
021 = 00-10-01 = 9
022 = 00-10-10 = 10
023 = 00-10-11 = 11
030 = 00-11-00 = 12
031 = 00-11-01 = 13
032 = 00-11-10 = 14
033 = 00-11-11 = 15
100 = 01-00-00 = 16
101 = 01-00-01 = 17

4進数 ＝ ２進数 ＝10進数
２進数は判りやすいように２桁毎にハイフンで区切って表示してます。
8進数の場合は、３桁区毎にハイフンで区切れば同じような表が出来ます

これと同じ表を、３進数で作るとどうなるか
000 = 00-00-00 ＝ 00-00-00 = 0
001 = 00-00-01 ＝ 00-00-01 = 1
002 = 00-00-10 ＝ 00-00-10 = 2
010 = 00-01-00 ≠ 00-00-11 = 3
011 = 00-01-01 ≠ 00-01-00 = 4
012 = 00-01-10 ≠ 00-01-01 = 5
020 = 00-10-00 ≠ 00-01-10 = 6
021 = 00-10-01 ≠ 00-01-11 = 7
022 = 00-10-10 ≠ 00-10-00 = 8
100 = 01-00-00 ≠ 00-10-01 = 9
101 = 01-00-01 ≠ 00-10-10 = 10
102 = 01-00-10 ≠ 00-10-11 = 11
110 = 01-01-00 ≠ 00-11-00 = 12
111 = 01-01-01 ≠ 00-11-01 = 13
112 = 01-01-10 ≠ 00-11-10 = 14
210 = 10-01-00 ≠ 00-11-11 = 15
211 = 10-01-01 ≠ 01-00-00 = 16
212 = 10-01-10 ≠ 01-00-01 = 17

こうなります

お礼

回答有り難うございます。
様々な例をお書きくださり、有り難うございました。参考にさせていただきます。

回答No.3

m0r1_2006

４倍して，元の数を引けば　３倍になるし，
４倍して，元の数を足せば　５倍になる．
速いかどうかは，分かりかねるが

お礼

回答有り難うございます。
確かに、４倍して元の数を引けば３倍になりますね。
ただ、上記のプログラムを活用して、具体的にどうすれば良いでしょうか？
お手数をお掛けしますが、教えていただけないでしょうか？
よろしくお願いいたします。

回答No.2

NNori

ビットシフトとは、２倍（または1/2）することです。
つまり２回やれば４倍、３回やれば８倍することができます。
逆に言えば３倍や５倍はビットシフトしてもできません。

お礼

回答有り難うございます。
やっぱり、ビットシフトを使って３倍や５倍することは原理的に無理なんですね。

回答No.1

Tacosan

「ビットシフトを使った方が非常に計算が高速で出来る」って, 本当なの?

3進数や 5進数だと「ビッチシフトだけでは不可能」ってのは理解できてるよね?

お礼

回答有り難うございます。

> 3進数や 5進数だと「ビッチシフトだけでは不可能」ってのは理解
> できてるよね?

おっしゃる通り、無理だろうと思っていました。しかし、自分の知らない知識を使って工夫すれば可能かもしれないと期待していました。そこで、質問した次第です。