1

给定一堆整数，我想将它们转换为以 n 为基数，并且对于每个位，将这些位相加并将它们修改为 n。

示例：设 n = 3，假设我想在 4、4、4、2 中添加 mod 3 位。以 3 为底的这些数字是 11、11、11、02。最低有效位加起来为 1 + 1 + 1 + 2 = 5 = 2 mod 3。第二个最低有效位加起来为 1 + 1 + 1 + 0 = 3 = 0 mod 3。答案是 02 base 3 = 2。或者，如果我们没有在加法之前转换为基数 3，并且只是以二进制形式进行，我们有 100、100、100、010。从最低有效位到最高有效位的结果位是：0 + 0 + 0 + 0 = 0 mod 3, 0 + 0 + 0 + 1 = 1 mod 3, 1 + 1 + 1 + 0 = 0 mod 3，所以答案是 010 = 2。

n = 2 的情况非常简单，您可以对所有内容进行 XOR。有没有办法概括这一点？

4

2 回答 2

1

这是 ruby​​ 中的一首小曲：

#! /usr/bin/env ruby

def naryxor(n, terms)
  puts "Calculating the #{n}-ary XOR of #{terms.join(", ")}..."
  raise "Negative terms are forbidden" if terms.any? { |i| i < 0 }
  xor = []                    # "Digits" of our n-ary xor result

  done = false
  while not done
    done = true               # Assume we're done until proven otherwise
    xor.insert(0, 0)          # Insert a new total digit at the front

    terms = terms.select { |i| i > 0 }.collect do |i|
      done = false            # Not all remaining terms were zero

      digit = i % n           # Find the least n-ary digit
      rest = (i - digit) / n  # shift it off
      xor[0] += digit         # add it to our xor

      rest                    # Replace this integer with its remainder
    end

    xor[0] %= n               # Take the mod once, after summing.
  end

  xor[1..-1]                  # Drop untouched leading digit
end

raise "Usage: ./naryxor.rb arity term term..." if ARGV.size <= 1
puts naryxor(ARGV[0].to_i, ARGV[1..-1].collect(&:to_i)).join("")

运行它：

$ ./naryxor.rb 3 4 4 4 2
Calculating the 3-ary XOR of 4, 4, 4, 2...
02

这只是扩展n-ary传递的整数的表示并做一些愚蠢的事情。如果n被认为是 2 的幂，我们可以做一些更有趣的位旋转来避免整数除法，但你没有给出这样的保证。

于 2012-08-12T02:26:06.777 回答
0

我不认为有一个数学属性可以导致有效的通用捷径。XOR 适用于 base 2 的原因是因为 XOR 具有方便的特性，即与进位丢弃相加。

一个简单的递归函数可以应用该算法，例如利用 Scala 的 BigInt 类进行基本转换：

def sums(radix: Int, digits: List[List[String]]): String =
  if(digits exists { _.nonEmpty }) // there's at least 1 bit left to add
    (digits.flatMap { _.headOption } // take the 1st bit of all numbers
      .map { BigInt(_, radix) } // convert to int representation
      .sum
      .toInt % radix // modulo by base
    ).toString +
    sums(radix, digits map { _.drop(1) }) // do next most significant bit
  else 
    "" // base case: no digits left to add

def sum(radix: Int, ns: List[Int]): Int =
  BigInt(
    sums(
      radix,
      ns // use BigInt to convert from int representation to string 
        .map { BigInt(_) }
        .map { _.toString(radix).split("").drop(1).toList.reverse }
    )
    .reverse,
    radix
  ).toInt

scala> sum(3, List(4,4,4,2))
res0: Int = 2

您的问题被标记为“性能”，但没有列出任何关于内存或运行时的额外限制来告知改进的方法。

于 2012-08-12T02:11:56.243 回答