1

整数の束が与えられた場合、それらを基数 n に変換し、ビットごとにビットを加算して n で mod します。

例: n = 3 とし、3 を法とするビットを 4、4、4、2 に追加するとします。これらの数値は 3 進数で 11、11、11、02 です。最下位ビットは 1 + 1 になります。 + 1 + 2 = 5 = 2 mod 3. 2 番目の最下位ビットは 1 + 1 + 1 + 0 = 3 = 0 mod 3 になります。答えは 02 base 3 = 2 です。加算の前に基数 3 に変換し、2 進数でそれを行ったところ、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

これがルビーのちょっとしたことです：

#! /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これは、渡された整数の表現を拡張するだけで、ばかげたことをします。が 2 の累乗である場合n、整数除算を回避するためにさらに興味深いビット操作を行うことができますが、そのような保証はありませんでした。

于 2012-08-12T02:26:06.777 に答える
0

効率的な一般的なショートカットにつながる数学的特性はないと思います。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-12T02:11:56.243 に答える