Rubyでの10進数変換処理
Rubyでは、to_i メソッドに基底（2進数の場合は、2）を引数に指定して、実行することにより10進数に変換が出来ます。
irb(main):001> "100".to_i(2)
=> 4
右桁から計算するのが一番直感的ですが、
target_str = '101'
reversed_target_str = target_str.reverse!
base = 2
total_decimal = 0
reversed_target_str.each_char.with_index do |target_char, index|
target_int = target_char.to_i
decimal_value = target_int * (base ** index)
total_decimal += decimal_value
end
Ruby内部ではどのように計算されているのでしょうか。
Rubyのソースコード確認
Rubyで書かれている処理
string.rbのto_i メソッドを確認しても、10進数への変換処理が書かれていないです。
string.rb
# Returns the result of interpreting leading characters in +self+
# as an integer in the given +base+ (which must be in (2..36)):
#
# '123456'.to_i # => 123456
# '123def'.to_i(16) # => 1195503
#
# Characters past a leading valid number (in the given +base+) are ignored:
#
# '12.345'.to_i # => 12
# '12345'.to_i(2) # => 1
#
# Returns zero if there is no leading valid number:
#
# 'abcdef'.to_i # => 0
# '2'.to_i(2) # => 0
def to_i(base = 10) end
string.rbs を参照することにより、string.cに処理が書かれていることが分かります。
string.rbs
# <!--
# rdoc-file=string.c
# - to_i(base = 10) -> integer
# -->
# Returns the result of interpreting leading characters in `self` as an integer
# in the given `base` (which must be in (0, 2..36)):
#
# '123456'.to_i # => 123456
# '123def'.to_i(16) # => 1195503
#
# With `base` zero, string `object` may contain leading characters to specify
# the actual base:
#
# '123def'.to_i(0) # => 123
# '0123def'.to_i(0) # => 83
# '0b123def'.to_i(0) # => 1
# '0o123def'.to_i(0) # => 83
# '0d123def'.to_i(0) # => 123
# '0x123def'.to_i(0) # => 1195503
#
# Characters past a leading valid number (in the given `base`) are ignored:
#
# '12.345'.to_i # => 12
# '12345'.to_i(2) # => 1
#
# Returns zero if there is no leading valid number:
#
# 'abcdef'.to_i # => 0
# '2'.to_i(2) # => 0
#
def to_i: (?int radix) -> Integer
C言語で実装されている処理
rubyでのto_iはrb_str_to_iを呼び出していることが分かります。
string.c
rb_define_method(rb_cString, "to_i", rb_str_to_i, -1);
string.c
/*
* call-seq:
* to_i(base = 10) -> integer
*
* Returns the result of interpreting leading characters in +self+
* as an integer in the given +base+ (which must be in (0, 2..36)):
*
* '123456'.to_i # => 123456
* '123def'.to_i(16) # => 1195503
*
* With +base+ zero, string +object+ may contain leading characters
* to specify the actual base:
*
* '123def'.to_i(0) # => 123
* '0123def'.to_i(0) # => 83
* '0b123def'.to_i(0) # => 1
* '0o123def'.to_i(0) # => 83
* '0d123def'.to_i(0) # => 123
* '0x123def'.to_i(0) # => 1195503
*
* Characters past a leading valid number (in the given +base+) are ignored:
*
* '12.345'.to_i # => 12
* '12345'.to_i(2) # => 1
*
* Returns zero if there is no leading valid number:
*
* 'abcdef'.to_i # => 0
* '2'.to_i(2) # => 0
*
*/
static VALUE
rb_str_to_i(int argc, VALUE *argv, VALUE str)
{
int base = 10;
if (rb_check_arity(argc, 0, 1) && (base = NUM2INT(argv[0])) < 0) {
rb_raise(rb_eArgError, "invalid radix %d", base);
}
return rb_str_to_inum(str, base, FALSE);
}
rb_str_to_inum内に行くと、最終的には
util.cのruby_scan_digits関数に辿り着きます。
util.c
const signed char ruby_digit36_to_number_table[] = {
/* 0 1 2 3 4 5 6 7 8 9 a b c d e f */
/*0*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*1*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*2*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*3*/ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,-1,-1,-1,-1,-1,-1,
/*4*/ -1,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,
/*5*/ 25,26,27,28,29,30,31,32,33,34,35,-1,-1,-1,-1,-1,
/*6*/ -1,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,
/*7*/ 25,26,27,28,29,30,31,32,33,34,35,-1,-1,-1,-1,-1,
/*8*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*9*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*a*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*b*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*c*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*d*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*e*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
/*f*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
};
NO_SANITIZE("unsigned-integer-overflow", extern unsigned long ruby_scan_digits(const char *str, ssize_t len, int base, size_t *retlen, int *overflow));
unsigned long
ruby_scan_digits(const char *str, ssize_t len, int base, size_t *retlen, int *overflow)
{
RBIMPL_ASSERT_OR_ASSUME(base >= 2);
RBIMPL_ASSERT_OR_ASSUME(base <= 36);
const char *start = str;
unsigned long ret = 0, x;
unsigned long mul_overflow = (~(unsigned long)0) / base;
*overflow = 0;
if (!len) {
*retlen = 0;
return 0;
}
do {
int d = ruby_digit36_to_number_table[(unsigned char)*str++];
if (d == -1 || base <= d) {
--str;
break;
}
if (mul_overflow < ret)
*overflow = 1;
ret *= base;
x = ret;
ret += d;
if (ret < x)
*overflow = 1;
} while (len < 0 || --len);
*retlen = str - start;
return ret;
}
n進数を10進数に変換する処理だけを抜き出す
do {
int d = ruby_digit36_to_number_table[(unsigned char)*str++];
// 一部割愛
ret *= base;
// 一部割愛
ret += d;
// 一部割愛
} while (len < 0 || --len);
2進数 "100"を10進数に変換する処理を考えてみます。
int d = ruby_digit36_to_number_table[(unsigned char)*str++];
ruby_digit36_to_number_table配列は、ASCII文字をその対応する整数値にマッピングします。
'0'は0に、'1'は1にマッピングされます。
ret *= base;
ここで、現在の結果に基数（この場合は2）を掛けます。次の桁に移動するための重みを付けています。
ret += d;
ここで、新たに取得した数値を現在の結果に加えます。
このループは、文字列のすべての文字に対して実行されます。
例えば、"100"という文字列では、ループは3回実行されます。
各イテレーション後の変数の値は次のようになります
ret: 0
base: 2
1回目：
d: 1
ret *= base: 0
ret += d: 1
2回目：
d: 0
ret *= base: 2
ret += d: 2
3回目：
d: 0
ret *= base: 4
ret += d: 4
となり、4を返します。
n進数を10進数に変換する処理は
Rubyでは、左桁から重みを掛けていって、計算していることが分かります。
まとめ
Rubyでは10進数への変換処理は、左桁から計算していること（逐次変換法）が分かります。
右桁からの計算と違い、ループの途中までの計算結果を内部保存しておけば、
100
1001
10011
などリアルタイムに次の桁を入力された場合にも対応出来そうです。