将十进制数转换为N进制数的算法

Question

将十进制数转换为N进制数的算法

10

我正在寻找一种将十进制数转换为基数N的方法，其中N可以很大。具体而言，我正在考虑将其转换为基数85，然后再转换回来。有没有人知道执行转换的简单算法？理想情况下，它应该提供以下内容：

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

欢迎提出任何想法！

Roja

- Roja Buck

8个回答

3

这个的伪代码非常简单。将无符号整数转换为85进制：

digits := '';
while (number > 0)
  digit := number % 85
  digits := base85Digit(digit) + digits
  number /= 85 // integer division so the remainder is rounded off
end while

转换为十进制：

mult := 1
result := 0
for each digit in digits // starting from the rightmost working left
  result += base10(digit) * mult
  mult *= 85
end for

- cletus

1

请注意，"number /= 85" 被处理为整数除法，因此必须截断余数。 - Chris J

我可能错了，但是应该是 while (number > 85) 而不是 while (number > 0) 吧？ - ChrisInEdmonton

2

这是一个通用的伪代码算法：

初始化空列表
将当前数字对基数取模，将结果存储在列表前面
将当前数字除以基数并向下取整（整数除法可以完美地实现这一点）
如果结果仍大于零，则重复执行第2步

- Amber

如此简单明了 - Jasand Pruski

0

Base 85特别适用于ASCII编码的二进制数据，我猜这也是您使用它的原因。(然而，如果是这样，您应该问自己是否值得这么麻烦，以及Base 64是否不够好。)

如果您将其用作编码方案，那么您的工作就是将整数(4字节)转换为5个Base85数字组。(如何处理不是4字节倍数的东西取决于您--通常末尾会用零填充。请参阅Base 85的维基百科页面获取详细信息。)

基本算法非常简单：在打包到基于85的编码时取余数，然后重复分割并计算，直到完成。要返回，请重复添加值并乘以85，直到完成。我对Ruby不是特别熟悉，所以这里的代码是C/C++/Java风格的，希望您能理解：

// To base 85
unsigned int n = // your number
byte b85[5]; // What you want to fill
for (int i=0 ; i<5 ; i++) {
  b85[4-i] = (n%85);  // Fill backwards to get most significant value at front
  n = n/85;
}

// From base 85
n = 0;
for (int i=0 ; i< 5 ; i++) {
  n = n*85 + b85[i];
}

这是无需担心溢出，无需担心添加33以进入ASCII范围，也无需担心零被编码为!!!!!而不是z等约定。

- Rex Kerr

0

因为我觉得递归在我给出的答案中没有得到充分体现，所以我提供下面的草稿

def to_radix(int, radix)
  int == 0 ? [] : (to_radix(int / radix, radix) + [int % radix])
end

- Emirikol

0

83992 / 85 = 988, reminder 12

988   / 85 = 11,  reminder 53

11   /  85 = 0,   reminder 11

将提醒按相反顺序排列：11、53、12，以获得您的85进制数。

要将其恢复：

11 * 85^2 + 53 * 85^1 + 12 * 85^0 = 83992

- Yin Zhu

0

我能想到的最简单的算法是（伪代码）：

N = base-10 number
1) N mod 85 = 1st number
2) tempVal = floor(N/85)
3) if(tempVal > 0 && tempVal < 85) then
    tempVal= 2nd number
else
    2nd number = (tempVal mod 85), then goto step (2), replacing N with N1

- Mark M

-1

Fixnum#to_s对您没有帮助，因为它只能达到base 36。

我很惊讶您要使用基数85。您能解释一下基数是如何工作的吗？

- Andrew Grimm

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jörg W Mittag · Accepted Answer

那是一个有趣的问题，所以我有点过度了：

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地址视为基数256的数字，并使用身份映射和'.'作为分隔符来格式化它：

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