?
Solved

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

Posted on 2003-02-19
3
Medium Priority
?
476 Views
Last Modified: 2011-09-20
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

About the method:
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
Comment
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
  • Learn & ask questions
3 Comments
 
LVL 22

Expert Comment

by:grg99
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

by:
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

by:FaithRaven
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
Please leave any comments here within the next seven days.

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

FaithRaven
EE Cleanup Volunteer
0

Featured Post

Optimize your web performance

What's in the eBook?
- Full list of reasons for poor performance
- Ultimate measures to speed things up
- Primary web monitoring types
- KPIs you should be monitoring in order to increase your ROI

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

770 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question