用于将基数10转换为基数N的算法

Question

我正在寻找一种方法将基数为10的数字转换为基数为N的数字,其中N可以很大.具体来说,我正在寻找转换到base-85并再次返回.有谁知道一个简单的算法来执行转换？理想情况下它会提供如下内容:

to_radix(83992, 85) -> [11, 53, 12]

任何想法都表示赞赏!

罗亚

Answer 1

这是一个有趣的问题,所以我有点过分了:

class Integer
  def to_base(base=10)
    return [0] if zero?
    raise ArgumentError, 'base must be greater than zero' unless base > 0
    num = abs
    return [1] * num if base == 1
    [].tap do |digits|
      while num > 0
        digits.unshift num % base
        num /= base
      end
    end
  end
end

这适用于任意基础.它只适用于整数,虽然没有理由不能将其扩展为使用任意数字.此外,它忽略了数字的符号.同样,没有理由为什么它必须这样做,但主要是我不想要提出一个约定来返回返回值中的符号.

class Integer
  old_to_s = instance_method(:to_s)
  define_method :to_s do |base=10, mapping=nil, sep=''|
    return old_to_s.bind(self).(base) unless mapping || base > 36
    mapping ||= '0123456789abcdefghijklmnopqrstuvwxyz'
    return to_base(base).map {|digit| mapping[digit].to_s }.join(sep)
  end
end

[Fixnum, Bignum].each do |klass|
  old_to_s = klass.instance_method(:to_s)
  klass.send :define_method, :to_s do |base=10, mapping=nil, sep=''|
    return old_to_s.bind(self).(base) unless mapping || base > 36
    return super(base, mapping, sep) if mapping
    return super(base)
  end
end

我还扩展了to_s方法,使其适用于大于36的基数.如果要使用大于36的基数,则必须传入将"数字"映射到字符串的映射对象.(嗯,实际上,所需要的只是你提供一个响应的对象[]并返回响应的东西to_s.所以,一个字符串是完美的,但是例如一个整数数组也可以工作.)

它还接受一个可选的分隔符,用于分隔数字.

例如,这允许您通过将IPv4地址视为base-256数字并使用映射的标识并将其'.'作为分隔符来格式化IPv4地址:

2_078_934_278.to_s(256, Array.new(256) {|i| i }, '.') # => '123.234.5.6'

这是一个(不完整的)测试套件:

require 'test/unit'
class TestBaseConversion < Test::Unit::TestCase
  def test_that_83992_in_base_85_is_11_53_12
    assert_equal [11, 53, 12], 83992.to_base(85)
  end
  def test_that_83992_in_base_37_is_1_24_13_2
    assert_equal [1, 24, 13, 2], 83992.to_base(37)
  end
  def test_that_84026_in_base_37_is_1_24_13_36
    assert_equal [1, 24, 13, 36], 84026.to_base(37)
  end
  def test_that_0_in_any_base_is_0
    100.times do |base|
      assert_equal [0], 0.to_base(base)
      assert_equal [0], 0.to_base(1 << base)
      assert_equal [0], 0.to_base(base << base)
    end
  end
  def test_that_84026_in_base_37_prints_1od_
    assert_equal '1od_', 84026.to_s(37, '0123456789abcdefghijklmnopqrstuvwxyz_')
  end
  def test_that_ip_address_formatting_works
    addr = 2_078_934_278
    assert_equal '123.234.5.6', addr.to_s(256, (0..255).to_a, '.')
    assert_equal '123.234.5.6', addr.to_s(256, Array.new(256) {|i| i}, '.')
  end
  def test_that_old_to_s_still_works
    assert_equal '84026', 84026.to_s
    assert_equal '1su2', 84026.to_s(36)
  end
end