Solved

# Finding the bit/bits from one digit which different it from group of other digits (Kazakow method)

Posted on 2003-02-19
Medium Priority
476 Views
The method is generally called Kazakow and I'm looking for
C/C++ implementation or even help where to find it or how it may work

We have one digit(F0) and a group of other digits(F1).

F0=0110

F1=1000,
1001,
0011,

We want to find the bit/bits which different F0 and F1.
The result must contains the fewest bits which different them
so the answer is -1-- (bit 3) - only one bit in this exapamle !!

_generaly for ONE bit

for i := 1 to n do {numbers of bits}
begin
{ here I compare F0 and F1 }
{ by the bit number i }
end;
---------
_for TWO bit

for i := 1 to n-1 do
begin
for j :=i+1 to n do
begin
{ here I compare F0 and F1 }
{ by the bit number "i" and bit "j"}
end;
---------
but how to find n-bits which different them ?!
this situations accurs in Karnaugh grid where '1' is
rounded with '0'

What for this example ?!
F0=01111

F1=00111,
01011
01101,
01110,
11111

what if I have 20-bits digits ?!

I think that some sort of adding items or even recuration is here needed

Any suggestions ?

Peter
0
Question by:kurzbauer
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 22

Expert Comment

ID: 7982387
I'm not quite sure I understand the problem, but if you want to find the bits that differ in two words, all you have to do is:

a = 0010101110110101;
b = 0000010110111000;

c = a XOR b;

c is now:
a = 0010101110110101;
b = 0000010110111000;
c = 0010111000001101;

'c' has all the bits that differ in a and b.

Now to find the number of bits that are different, you can do it two ways, slow and fast.

slow:  for( i=tot=0;i<WordWith;i++ ) tot += (c >> i) & 1;

This takes "WordWidth" loops.

If WordWidth is some reasonable number, like 16,
then you can use the slow method to precompute a table and just index into the table to look up the number of bits in c.

Hope this helps!

0

LVL 1

Accepted Solution

TheBeaver earned 280 total points
ID: 7984326
int Difference(int a, int b)
{
int d = a ^ b; // XOR
int c=0;

while( d )
{
c+= (d & 1);
d = d >> 1;
}
return c;
}

Same thing as what grg99 is saying but you don't need to know the widths.
0

LVL 3

Expert Comment

ID: 9307452
No comment has been added lately, so it's time to clean up this TA.
I will leave a recommendation in the Cleanup topic area that this question is:
Accept TheBeaver's comment

FaithRaven
EE Cleanup Volunteer
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Whether you've completed a degree in computer sciences or you're a self-taught programmer, writing your first lines of code in the real world is always a challenge. Here are some of the most common pitfalls for new programmers.
A short article about problems I had with the new location API and permissions in Marshmallow
Six Sigma Control Plans
Introduction to Processes
###### Suggested Courses
Course of the Month11 days, 5 hours left to enroll