CODEWITHSUNDEEP
c++cbit-manipulationxor
pantaryl
pantaryl

Reputation: 155

Fastest Way to XOR all bits from value based on bitmask?

I've got an interesting problem that has me looking for a more efficient way of doing things.

Let's say we have a value (in binary)

(VALUE) 10110001
(MASK)  00110010
----------------
(AND)   00110000

Now, I need to be able to XOR any bits from the (AND) value that are set in the (MASK) value (always lowest to highest bit):

(RESULT) AND1(0) xor AND4(1) xor AND5(1) = 0

Now, on paper, this is certainly quick since I can see which bits are set in the mask. It seems to me that programmatically I would need to keep right shifting the MASK until I found a set bit, XOR it with a separate value, and loop until the entire byte is complete.

Can anyone think of a faster way? I'm looking for the way to do this with the least number of operations and stored values.

Upvotes: 0

Views: 3364

Answers (4)

John Kugelman
John Kugelman

Reputation: 361635

If I'm understanding you right, you have

result = value & mask

and you want to XOR the 1 bits of mask & result together. The XOR of a series of bits is the same as counting the number of bits and checking if that count is even or odd. If it's odd, the XOR would be 1; if even, XOR would give 0.

count_bits(mask & result) % 2 != 0

mask & result can be simplified to simply result. You don't need to AND it with mask again. The % 2 != 0 can be alternately written as & 1.

count_bits(result) & 1

As far as how to count bits, the Bit Twiddling Hacks web page gives a number of bit counting algorithms.

Counting bits set, Brian Kernighan's way

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
  v &= v - 1; // clear the least significant bit set
}

Brian Kernighan's method goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop.

If you were to use that implementation, you could optimize it a bit further. If you think about it, you don't need the full count of bits. You only need to track their parity. Instead of counting bits you could just flip c each iteration.

unsigned bit_parity(unsigned v) {
  unsigned c;
  for (c = 0; v; c ^= 1) {
    v &= v - 1;
  }
}

(Thanks to Slava for the suggestion.)

Upvotes: 5

David C. Rankin
David C. Rankin

Reputation: 84561

One significant issue to be aware of if using v &= v - 1 in the main body of your code is it will change the value of v to 0 in conducting the count. With other methods, the value is changed to the number of 1's. While count logic is generally wrapped as a function, where that is no longer a concern, if you are required to present your counting logic in the main body of your code, you must preserve a copy of v if that value is needed again.

In addition to the other two methods presented, the following is another favorite from bit-twiddling hacks that generally has a bit better performance than the loop method for larger numbers:

/* get the population 1's in the binary representation of a number */
unsigned getn1s (unsigned int v)
{
    v = v - ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    v = (v + (v >> 4)) & 0x0F0F0F0F;
    v = v + (v << 8);
    v = v + (v << 16);
    return v >> 24;
}

Upvotes: 0

luiscubal
luiscubal

Reputation: 25121

If I understood this question correctly, what you want is to get every bit from VALUE that is set in the MASK, and compute the XOR of those bits.

First of all, note that XOR'ing a value with 0 will not change the result. So, to ignore some bits, we can treat them as zeros.

So, XORing the bits set in VALUE that are in MASK is equivalent to XORing the bits in VALUE&MASK.

Now note that the result is 0 if the number of set bits is even, 1 if it is odd.

That means we want to count the number of set bits. Some architectures/compilers have ways to quickly compute this value. For instance, on GCC this can be obtained with __builtin_popcount.

So on GCC, this can be computed with:

int set_bits = __builtin_popcount(value & mask);

return set_bits % 2;

If you want the code to be portable, then this won't do. However, a comment in this answer suggests that some compilers can inline std::bitset::count to efficiently obtain the same result.

Upvotes: 5

user555045
user555045

Reputation: 64904

Using that the XOR with 0 doesn't change anything, it's OK to apply the mask and then unconditionally XOR all bits together, which can be done in a parallel-prefix way. So something like this (not tested):

x = m & v;
x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x ^= x >> 1;
result = x & 1

You can use more (or fewer) steps as needed, this is for 32 bits.

Upvotes: 2

Related Questions