Fast Xoring

[Labdabeta]

Quick question (though I still want to get my long OpenGL question fixed) is there a faster way to Xor the bits of an integer than this:

(MyInt&0x1)^((MyInt&0x2)>>1)^((MyInt&0x4)>>2)//etcetera

Just to clarify by faster I mean faster to execute, not to type as this operation will have to be done many many times.

[StuXYZ]

I have a nice little bit of OLD code that I use to count the number of bits, and I have adapted the idea. [Note I didn't write the original idea of using 0333 and 0111, but I do not know who did].

unsigned int uCount = MyInt
    - ((MyInt >> 1) & 033333333333)
    - ((MyInt >> 2) & 011111111111);
  
   result=(uCount & 1);

It is about 3 times quicker on my computer. As with all of these things please benchmark it yourself, with your compiler and your optimizations flags etc.

The principle of the code is that it is clustering each number into little triplets of bits and the & 0333 and & 0111 part just keep the triplets isolated.

The double subtraction effectively sum the number of bits in a triple, by binary residual.

The & 1 at the end carries out the xor part of your code.

[Labdabeta]

I cant say I fully understand... the 0333333333 and 0111111111 are in what base?
Anyways, this sounds very clever!

[Labdabeta]

I just tested your code, it does not seem to work. TEST CASES:

TEST|EXPECTED|ACTUAL
~~~~~~~~~~~~~~~~~~~~
15  |       0|     1
63  |       0|     1
8   |       1|     0

[arkoenig]

Xoring the bits of an integer is equivalent to computing its parity. There are ways of doing so that might be faster than your original example, but you'd have to measure to see whether it's really faster in practice.

The way that comes to mind is this: Divide the integer into N-bit chunks. Use each chunk as an index into a table with 2^N elements that you have precomputed to hold the parity of each possible chunk. Then xor the table values together.

I would guess that 8, or perhaps 12 or 16, is a convenient number of bits. Beyond that you run the risk of depleting your processor's cache with table elements.

However, I need to emphasize again that unless you actually measure the code both ways, you won't know if it helps.

[nezachem]

I have a nice little bit of OLD code that I use to count the number of bits, and I have adapted the idea. [Note I didn't write the original idea of using 0333 and 0111, but I do not know who did].

unsigned int uCount = MyInt
    - ((MyInt >> 1) & 033333333333)
    - ((MyInt >> 2) & 011111111111);
  
   result=(uCount & 1);

You seem to miss the very important operation here:

uCount = ((uCount + (uCount >> 3)) & 030707070707) % 63;

after line 4.

[Labdabeta]

Thank you, the missing line worked!

[murnesty]

don't understand. Is there any clue or picture to show?