CODEWITHSUNDEEP
algorithmxor
Nitin Garg
Nitin Garg

Reputation: 2079

algorithm to calculate XOR

I want to calculate XOR of numbers from 0 to (n)^{1/2} - 1 with each of numbers from 0 to (n)^{1/2} - 1. i want to do this in O(n) time and cant use the XOR, OR, AND operations.

If i know the XOR of X and Y, can i calculate XOR of X+1 and Y in constant time?

As some have pointed out that XOR can be calculated in constant time using AND and NOT. How do i do the same for AND? How do i calculate AND of numbers from 0 to (n)^{1/2} - 1 with each of numbers from 0 to (n)^{1/2} - 1. i want to do this in O(n) time and cant use the XOR, OR, AND operations.

P.S. - RAM model is being assumed here and operations (add, multiply, divide) on < log(n) bit numbers can be done is constant time.

Upvotes: 2

Views: 3427

Answers (5)

cj rogers
cj rogers

Reputation: 96

if the two are not equal, then they are xor.

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

xorBooleans(boolean1,boolean2){
    return boolean1 != boolean2
}

Upvotes: 1

xanatos
xanatos

Reputation: 111940

A XOR can be built using AND and NOT (and combining them to build a NAND). Can you use AND and NOT?

In 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);
};

I'm mimicking this: http://en.wikipedia.org/wiki/NAND_logic#XOR

In C#, using modulus, sum and multiply. (Limits: I'm using uint, so max 32 bits. It will work for ulong, so max 64 bits)

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;
}

Where res is the response.

Modulus can be built on top of division, multiplication and subtraction.

Upvotes: 2

user97370
user97370

Reputation:

First, let k be the smallest power of 2 greater than or equal to sqrt(n). k is still O(sqrt(n)) so this won't change the complexity.

To construct the full k by k table, we construct it one row at a time.

We start with the 0th row: this is easy, because 0 xor j = j.

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

Next, we go over the rows in gray-code order. The gray-code is a way of counting every number from 0 to one-less than a power of 2 by changing one bit at a time.

Because of the gray-code property, we're changing the row number by 1 bit, so we have an easy job computing the new row from the old since the xors will only change by 1 bit.

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

We need some functions to help us here. First a function that finds the first bit that's different.

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

We need a function that changes a bit in O(1) time.

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

Finally, the tricky bit: counting in gray codes. From wikipedia, we can read that an easy gray code can be obtained by computing 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

Note that the slow_xor is O(number of bits in a and b), but that's ok here since we're not using it in the inner loop of the main function.

Upvotes: 0

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272802

Yes.

Start with a [1x1] grid:

H(-1) = [ 0 ]

Then apply the recursion:

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

where that denotes matrix concatenation. i.e. each recursion doubles the size of the grid in each dimension. Repeat until you achieve the required size.

Upvotes: 2

Bojangles
Bojangles

Reputation: 101543

You can build an XOR gate from NANDs (diagram here), so you could do it with an if statement with ! (NOT) and && AND (if we use C/C++/PHP as an example here). As for working it out in a constant time, the calculation is the same every iteration, so it will be constant.

Upvotes: 2

Related Questions