Link to home
Start Free TrialLog in
Avatar of kurzbauer
kurzbauer

asked on

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

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
Avatar of grg99
grg99

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!

ASKER CERTIFIED SOLUTION
Avatar of TheBeaver
TheBeaver

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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