Is there any XOR bit reduction operand or function?

Question

Is there any XOR bit reduction operand or function in python? I have no problem to write it by yourself, but there's no reason to write it in every script if there's already built-in.

r=x&1
for i in xrange(1,63):
    r=r^((x>>i)&1)

Answer 1

this doesn't answer your question but that code is the same as:

def parity(x):
    k = 0
    d = x
    while d != 0:
        k = k + 1
        d = d & (d - 1)
    return k % 2

which has the benefit of not depending on the bit length of the number; and is faster (e.g. on 2**62 yours takes 46.6 usec and this takes 3.02 usec) because the loop depends on the number of ones (i.e. the population count) in the number not the number of bits.

Answer 2

Basically, this is the same as asking if the number of 1's in x is even or odd, which is the same as asking what is the parity of x.

The solution you gave is indeed the naive solution, and is horribly inefficient compared to other methods. Here is a site with some excellent solutions for this and other bit-related problems: Bit twiddling hacks.
The solutions there are given in c, but it shouldn't be hard to "translate" them into python.

Answer 3

If you don't mind using an external module, you could use bitstring's count() method.

If you just want a concise Python expression, try

r = sum(map(int, format(x, "b"))) & 1

Answer 4

Just for fun, here's another version of @Sven Marnach's answer.

r = sum(ord(ch) for ch in format(x, "b")) & 1

This works in ASCII and thus in Unicode. The reason it works is because the ordinal value of '0' is 0x30, which has a 0 bit in the least significant bit position; while the ordinal value of '1' is 0x31, which has a 1 bit there. If we are just going to bitwise-and with the least significant bit anyway, this will work just as well as using int() to coerce a '1' or a '0' into an bit value.

This is over twice as fast! But @Dan D.'s answer is even faster. Computing the parity of all numbers in xrange(200000), best of three trials:

@Sven Marnach's answer:  1.550 seconds
this answer:             0.605 seconds
@Dan D.'s answer:        0.411 seconds

And with more trials (larger numbers to compute), @Dan D.'s answer would win by a larger margin.

Answer 5

I don't think that exactly what you want exists. I did discover a module you might find useful: the bitstring module.

http://code.google.com/p/python-bitstring/

I was going to suggest using bitstream to pull bits off one at a time, and then use operator.xor() inside the reduce() function to solve your problem. But I think you can't beat the while loop that finds parity efficiently.