xorspaceを探検する

整数セットの xorspace は、開始整数を普通のビット単位のxor演算子( ^
)と組み合わせることによって得られるすべての整数の集合です。たとえば、(8,4)のxorspaceは(0,4,8,12)です.0は4
^ 4、12は4 ^ 8、いいえ他の数に達することができます。この定義では、開始番号は常に含まれています(たとえば、4は4 ^ 4 ^
4)。

あなたの目標は、負でない整数のリストを入力とする最短のプログラムを書いて、xorspaceの要素の数を出力することです。


  • Standard loopholes
    are forbidden.
  • Input and output can be in any of the
    usual formats
    . Input is guaranteed to be valid, non-empty, and
    without duplicates.
  • Your code should be able to process all テストケース in less
    than a day
    .

テストケース

Input: 0
Output: 1

Input: 6
Output: 2

Input: 8 4
Ouput: 4

Input: 0 256
Output: 2

Input: 256 259 3
Output: 4

Input: 60 62 94 101 115
Output: 32

Input: 60 62 94 101 115 40 91
Output: 32

Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
Output: 64

Input: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384
Output: 32768
ベストアンサー

MATL, 11 bytes

t"G!Z~Ghu]n

オンラインで試してみてください!

最後のテストケースは、メモリの制限のためオンラインインタープリタでは実行されませんが、最新のコンピュータでは2秒未満でオフラインで実行されます。

説明

n サイズの入力の場合、これは次のようになります。

  1. Initiallize result to input.
  2. Repeat n times:
    1. Apply bitwise XOR to all pair of entries from current result
      and input.
    2. Attach input values to the result.
    3. Deduplicate.
  3. The output is the number of elements of the final result.

コメントしたコード。

t      % Implicit input: row vector. Duplicate
"      % For each (i.e. do as many times as the input size)
  G!   %   Push input as a column vector
  Z~   %   Bitwise XOR with broadcast, i.e. for all pairs of entries of the
       %   two arguments. The first argument is the accumulated result
       %   from the previous iteration, the second is the input vector
  G    %   Push input again
  h    %   Postpend
  u    %   Unique values. Gives a row vector
]      % End
n      % Number of entries. Implicitly display

入力 [256 259 3] の中間結果(ステップ2.1と2.3)は次のとおりです。

最初の繰り返し: [256 259 3][256 259 3]
:ビットごとのXORのすべてのペアを計算すると、

  0   3 259
  3   0 256
259 256   0

[256 259 3] を添付して重複排除する

0 3 259 256

2番目の反復: [256 259 3] での現在の結果 [0 3 259
256]
これを重複除外した後、再び

0 3 259 256

3回目の繰り返し:再び

0 3 259 256

したがって、出力は 4 (結果のエントリ数)です。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です