C++: compute a number's complement and its number of possible mismatches
- by Eagle
I got a bit stuck with my algorithm and I need some help to solve my problem. I think an example would explain better my problem.
Assuming:
d = 4 (maximum number of allowed bits in a number, 2^4-1=15).
m_max = 1 (maximum number of allowed bits mismatches).
kappa = (maximum number of elements to find for a given d and m, where m in m_max)
The main idea is for a given number, x, to compute its complement number (in binary base) and all the possible combinations for up to m_max mismatches from x complement's number.
Now the program start to scan from i = 0 till 15.
for i = 0 and m = 0, kappa = \binom{d}{0} = 1 (this called a perfect match)
possible combinations in bits, is only 1111 (for 0: 0000).
for i = 0 and m = 1, kappa = \binom{d}{1} = 4 (one mismatch)
possible combinations in bits are: 1000, 0100, 0010 and 0001
My problem was to generalize it to general d and m. I wrote the following code:
#include <stdlib.h>
#include <iomanip>
#include <boost/math/special_functions/binomial.hpp>
#include <iostream>
#include <stdint.h>
#include <vector>
namespace vec {
typedef std::vector<unsigned int> uint_1d_vec_t;
}
int main( int argc, char* argv[] ) {
int counter, d, m;
unsigned num_combination, bits_mask, bit_mask, max_num_mismatch;
uint_1d_vec_t kappa;
d = 4;
m = 2;
bits_mask = 2^num_bits - 1;
for ( unsigned i = 0 ; i < num_elemets ; i++ ) {
counter = 0;
for ( unsigned m = 0 ; m < max_num_mismatch ; m++ ) {
// maximum number of allowed combinations
num_combination = boost::math::binomial_coefficient<double>( static_cast<unsigned>( d ), static_cast<unsigned>(m) );
kappa.push_back( num_combination );
for ( unsigned j = 0 ; j < kappa.at(m) ; j++ ) {
if ( m == 0 )
v[i][counter++] = i^bits_mask; // M_0
else {
bit_mask = 1 << ( num_bits - j );
v[i][counter++] = v[i][0] ^ bits_mask
}
}
}
}
return 0;
}
I got stuck in the line v[i][counter++] = v[i][0] ^ bits_mask since I was unable to generalize my algorithm to m_max1, since I needed for m_max mismatches m_max loops and in my original problem, m is unknown until runtime.
