Bitwise Partial Match

[cpnet]

I have a known binary value, and I want to match it to other binary values
when a certain number of the same bits in both values are 1. For example,
if I have the known value 0111, I want it to match any other 4-bit value
that has at least 2 of the same bits set to 1. In other words, 0111 would
match:

0111
0110
0101
0011
1011
1101
1110
1111


0111 would NOT match:

0000
0001
0010
0100
1000
1001
1010
1100


Are there any efficient operators/expressions I can use to figure out the
number of matching bits between 2 values? I'm trying to figure out
something with the bitwise operators or some math operators. I'd like to
avoid iterating though and manually comparing every bit.

I know ahead of time the total number of bits to compare, and the number of
bits set to 1 in each of the two values I'll be comparing. The tough part
is finding the count of bits set to 1 that they have in common.


Thanks.

 

[Mattias Sjögren]

Are there any efficient operators/expressions I can use to figure out the

number of matching bits between 2 values?

Here's a bunch of bit counting algorithms

http://www-db.stanford.edu/~manku/bitcount/bitcount.html

Just use one of them on the result of (value1 & value2). If you're
always dealing with 4-bit numbers I'd probably use an array with 16
elements as a lookup table.


Mattias

 

[Chris Priede]

Hi,

I have a known binary value, and I want to match it to other binary
values when a certain number of the same bits in both values are 1.

Are there any efficient operators/expressions I can use to figure out
the number of matching bits between 2 values? I know ahead of time
the total number of bits to compare, and the number of bits set to 1
in each of the two values I'll be comparing. The tough part is finding
the count of bits set to 1 that they have in common.

It's an interesting problem. I hope it's not a homework assignment.

To find the common bits, you want to perform a bitwise AND on the two
values. If the result is 0, there were no common bits. If it is non-zero,
it will contain only the common bits set:

uint bits = v1 & v2;

Then we count bits, for which there can be several ways:

int count = 0;
for (; bits != 0; count++)
bits &= bits - 1;
return count;

This particular method, which is often attributed to Brian Kernighan, is
just as simple as the most common shift/test loop, but more clever in that
it loops only once for each _set_ bit, not each bit in the value. If you
are counting long patterns, there might be more performant ways to do that.
For your example values, this would be one of the best choices.

 

[cpnet]

That is very helpful. This is actually related to poker probabilites, so
I'm dealing with 52 bit values. A variation on the pre-computer 8 or 16 bit
algorithm will probably work best for me based on the test values in your
link, but I'm going to have to try them all out myself I think. Efficiency
will be key for me.

Thanks,
cpnet

 

[cpnet]

No, it's not a homework assignment. I'm looking at calculating poker
probabilites (I want to see if I can do a better job than some of the
existing tools out there). Your approach seems to be the 'sparse ones'
approach in Mattias' link. As I think more about it, I may just test all of
the approaches including the one below to see which works best for me. I
will have a few cases, all comparing 52-bit values. One value will always
have 5 bits set, and the others will have between 5 and 7 bits set.
Depending on the case, 3 to 5 of the bits will have to match. I suppose I
may even find that for each case, a different algorithm works better.

Thanks,
cpnet