2

0から（n）^ {1/2}-1までの数値のXORを、0から（n）^ {1/2}-1までの各数値で計算したい。これをO（n）で実行したい時間とXOR、OR、およびAND演算を使用できません。

XとYのXORがわかっている場合、一定時間でX + 1とYのXORを計算できますか？

一部の人が指摘しているように、XORはANDとNOTを使用して一定時間で計算できます。ANDに対して同じことをするにはどうすればよいですか？0から（n）^ {1/2} -1までの数値のANDを、0から（n）^ {1/2} -1までの数値のそれぞれで計算するにはどうすればよいですか？O（n）でこれを実行したい時間とXOR、OR、およびAND演算を使用できません。

PS-ここではRAMモデルが想定されており、<log（n）ビット数の演算（加算、乗算、除算）は一定時間で実行できます。

4

5 に答える 5

2

はい。

[1x1]グリッドから始めます。

H(-1) = [ 0 ]

次に、再帰を適用します。

H(i) = [ H(i-1)           H(i-1)+(1 << i)
         H(i-1)+(1 << i)  H(i-1)          ]

ここで、それは行列の連結を示します。つまり、再帰ごとに、各次元のグリッドのサイズが2倍になります。必要なサイズになるまで繰り返します。

于 2011-02-20T13:46:00.193 に答える
2

NANDからXORゲートを構築できるので（ここの図）、 （NOT）とAND（ここで例としてC / C ++ / PHPを使用する場合）を使用したifステートメントでそれを行うことができます。一定時間での計算に関しては、計算はすべての反復で同じであるため、一定になります。!&&

于 2011-02-20T12:16:52.100 に答える
2

XORは、ANDとNOTを使用して構築できます（そしてそれらを組み合わせてNANDを構築します）。ANDとNOTを使用できますか？

C＃の場合：

Func<bool, bool, bool> nand = (p, q) => !(p && q);

Func<bool, bool, bool> xor = (p, q) =>
{
    var s1 = nand(p, q);
    var s2a = nand(p, s1);
    var s2b = nand(q, s1);
    return nand(s2a, s2b);
};

私はこれを模倣しています：http：//en.wikipedia.org/wiki/NAND_logic#XOR

C＃では、モジュラス、合計、および乗算を使用します。（制限：私はuintを使用しているので、最大32ビットです。ulongでも機能するので、最大64ビットです）

uint a = 16;
uint b = 5;
uint mult = 1;
uint res = 0;

for (int i = 0; i < 32; i++)
{
    uint i1 = a % 2;
    uint i2 = b % 2;

    if (i1 != i2) {
        res += mult;
    }

    a /= 2;
    b /= 2;
    mult *= 2;
}

ここで、resは応答です。

モジュラスは、除算、乗算、減算の上に構築できます。

于 2011-02-20T12:19:14.303 に答える
1

2つが等しくない場合、それらはxorです。

xorBits(bit1,bit2){
     return bit1 != bit2?1:0
}

xorBooleans(boolean1,boolean2){
    return boolean1 != boolean2
}
于 2014-04-24T15:40:27.980 に答える
0

まず、kをsqrt（n）以上の2の最小の累乗とします。kはまだO（sqrt（n））であるため、複雑さは変わりません。

完全なkxkテーブルを作成するには、一度に1行ずつ作成します。

0行目から始めます。0xorj=jであるため、これは簡単です。

for i in xrange(k):
    result[0][i] = i

次に、行をグレイコード順に調べます。グレイコードは、一度に1ビットずつ変更することにより、0から1までのすべての数値をカウントする方法です。2の累乗未満です。

グレイコードプロパティのため、行番号を1ビット変更します。したがって、xorsは1ビットしか変更されないため、古い行から新しい行を簡単に計算できます。

last = 0
for row in graycount(k):
    if row == 0: continue
    bit_to_change = find_changed_bit(last, row)
    for i in xrange(k):
        result[row][i] = flip_bit(result[last][i], bit_to_change))
    last = row

ここで私たちを助けるためにいくつかの関数が必要です。最初に、異なる最初のビットを見つける関数。

def find_changed_bit(a, b):
    i = 1
    while True:
        if a % 2 != b % 2: return i
        i *= 2
        a //= 2
        b //= 2

O（1）時間で少し変化する関数が必要です。

def flip_bit(a, bit):
    thebit = (a // bit) % 2
    if thebit:
        return a - bit
    else:
        return a + bit

最後に、注意が必要なのは、グレイコードで数えることです。ウィキペディアから、xor（a、a // 2）を計算することで簡単なグレイコードを取得できることがわかります。

def graycount(a):
    for i in xrange(a):
        yield slow_xor(a, a // 2)

def slow_xor(a, b):
    result = 0
    k = 1
    while a or b:
        result += k * (a % 2 == b % 2)
        a //= 2
        b //= 2
        k *= 2
    return result

slow_xorはO（aとbのビット数）ですが、main関数の内部ループでは使用していないため、ここでは問題ありません。

于 2011-02-20T14:15:30.763 に答える