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

Question

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) AND₁(0) xor AND₄(1) xor AND₅(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.

What exactly are you trying to do? Can you write an equation that is more clear? — rlbond, Sep 23 '15 at 19:07
You want `(VALUE ^ XOR) & MASK`? Please be more specific. As given now, it is unclear what you want to accomplish. — too honest for this site, Sep 23 '15 at 19:07

score 5 · Answer 1 · edited May 23 '17 at 11:44

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.)}

Actually you can save another operation by changing the loop to `for (c = 0; v; c^=1)` then you do not need to do `&1` at the end :) — Slava, Sep 23 '15 at 19:50

score 5 · Accepted Answer · edited May 23 '17 at 11:58

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.

score 2 · Answer 3 · answered Sep 23 '15 at 18:52

2

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.

answered Sep 23 '15 at 18:52

harold

61,398
6
86
164

Maybe I misunderstood you, but XOR 0 is not a no-op. – ChronoTrigger Sep 23 '15 at 18:54
2

@ChronoTrigger why not? – harold Sep 23 '15 at 18:56
1 xor 0 = 1; 0 xor 0 = 0. – ChronoTrigger Sep 23 '15 at 18:57

score 0 · Answer 4 · answered Sep 23 '15 at 19:44

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

That's great (it is, really, nice method to count 1's) but why do that extra stuff to get the bit count when the full count isn't necessary? — harold, Sep 23 '15 at 20:21

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

4 Answers4

Counting bits set, Brian Kernighan's way