473,394 Members | 1,541 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,394 software developers and data experts.

Bitwise Partial Match

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.
Jan 14 '06 #1
4 1897
>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/bi.../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

--
Mattias Sjögren [C# MVP] mattias @ mvps.org
http://www.msjogren.net/dotnet/ | http://www.dotnetinterop.com
Please reply only to the newsgroup.
Jan 14 '06 #2
Hi,

cpnet wrote:
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.
--
Chris Priede


Jan 14 '06 #3
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

Jan 14 '06 #4
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


Jan 14 '06 #5

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

17
by: Paul MG | last post by:
Hi Template partial specialization always seems like a fairly straightforward concept - until I try to do it :). I am trying to implement the input sequence type (from Stroustrup section...
4
by: Erik Wikström | last post by:
In school (no I will not ask you to do my schoolwork for me) we talked about policy-based design and got an assignment where we got the a code- fragment from a stack-implementation. The idea with...
12
by: sandy_pt_in | last post by:
How to mulitply two integer numbers using bitwise operators in C language.Please reply as early as possible
2
by: Christian Staffe | last post by:
Hi, I would like to check for a partial match between an input string and a regular expression using the Regex class in .NET. By partial match, I mean that the input string could not yet be...
17
by: zirconx | last post by:
I'm trying to understand how the bitwise AND can be used. I've read about what it does but am having trouble applying it practically. I'm working on a system that somebody else wrote and they...
5
by: SQL Learner | last post by:
Hi Alex (Kuznetsov) and All, This is to follow up with my last post, "Link two tables using partial word match". How can I UPDATE table using partial word match? How can I write a SQL statement...
1
by: chungiemo | last post by:
Hi thought I would do another thread as this one is a bit different from the previous problem I am looking for a solution to the relating problem Comparing 2 access databases with 2 tables,...
1
by: tbucha3 | last post by:
I have two tables that I have to get information from to produce another table. Both tables come from separate resources, one has partial accounts with addresses and the other has complete account...
16
by: vorlonfear | last post by:
I have been working on this for a while now and I wanted to see if someone could assist me. I have 2 tables each with 5 fields. 4 of the fields are 2 character strings, then the final field is the...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
0
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
0
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers,...
0
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
0
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.