Two bit streams are given, differing from each other by no more than k bits.
How to ignore minor distortions, and find these threads the same?
Two bit streams are given, differing from each other by no more than k bits.
How to ignore minor distortions, and find these threads the same?
Try to write more detailed questions. To get an answer, explain what exactly you see the problem, how to reproduce it, what you want to get as a result, etc. Give an example that clearly demonstrates the problem. If the question can be reformulated according to the rules set out in the certificate , edit it .
Well, what's the difficulty? Here is a sketch:
unsigned int bit_count(unsigned int v) // Kerrighan way { unsigned int accum; for (accum = 0; v; accum++) v &= v - 1; return accum; } bool compare(seq s1, seq s2, unsigned int ignore_bits) { unsigned int rest_bits = ignore_bits; while (!s1.finished() || s2.finished()) { unsigned int curr1 = s1.current_int(), curr2 = s2.current_int(); unsigned int diff = curr1 ^ curr2; unsigned int different_bits = bit_count(diff); if (different_bits > rest_bits) return false; rest_bits -= different_bits; } return s1.finished() && s2.finished(); }
The solution may differ depending on how you want to interpret sequences of different lengths. Throw tail? To count missing bits as zeros? To consider missing bits as mismatched?
The solution uses an undefined seq
type representing the bit sequence. If you specify your type, you can also clarify the solution.
Source: https://ru.stackoverflow.com/questions/430173/
All Articles