M | C ++ implementation to find the mth smallest number having k number of set bits ; function to find the next higher number with same number of set bits as in ' x ' ; the approach is same as discussed in ; function to find the mth smallest number having k number of set bits ; smallest number having ' k ' number of set bits ; finding the mth smallest number having k set bits ; required number ; Driver program to test above
#include <bits/stdc++.h> NEW_LINE using namespace std ; typedef unsigned int uint_t ; uint_t nxtHighWithNumOfSetBits ( uint_t x ) { uint_t rightOne ; uint_t nextHigherOneBit ; uint_t rightOnesPattern ; uint_t next = 0 ; if ( x ) { rightOne = x & - ( signed ) x ; nextHigherOneBit = x + rightOne ; rightOnesPattern = x ^ nextHigherOneBit ; rightOnesPattern = ( rightOnesPattern ) / rightOne ; rightOnesPattern >>= 2 ; next = nextHigherOneBit | rightOnesPattern ; } return next ; } int mthSmallestWithKSetBits ( uint_t m , uint_t k ) { uint_t num = ( 1 << k ) - 1 ; for ( int i = 1 ; i < m ; i ++ ) num = nxtHighWithNumOfSetBits ( num ) ; return num ; } int main ( ) { uint_t m = 6 , k = 4 ; cout << mthSmallestWithKSetBits ( m , k ) ; return 0 ; }