最简单的方法来添加位mod n？

给定一串整数，我想将它们转换为基数n，并且对于每一位，将它们加起来并用n来修改它们。最简单的方法来添加位mod 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.或者，if我们在加法之前没有转换为基数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的一切。有没有办法来推广这个？

来源

2012-08-12 Popcorn

所以按'位'你的意思是'n-ary digit'？ – phs 2012-08-12 01:25:15

抱歉，我不确定你的意思。你能澄清吗？ – Popcorn 2012-08-12 01:27:12

技术上，如果它不是基数2，它们只是数字，而不是'位'（BInary digiTS） – 2012-08-12 01:27:24

这里的小曲在红宝石：

#! /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-12 02:26:06 phs

我不认为有一个数学属性导致高效的通用捷径。 XOR为基数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-12 02:11:56 cldellow

最简单的方法来添加位mod n？

回答

相关问题