I think this should be easy to understand.
#include<iostream>
using namespace std;
// this function generated next big number of the list having k bit set.
unsigned next_number( unsigned x)
{
unsigned smallest, ripple, one;
smallest = x & (-x);
ripple = x + smallest ;
one = ripple^x;
one = (one>>2)/smallest;
return ripple | one ;
}
// this function first set the initial to the first element of the list and
then call next_number function //(n-1) times to get nth element of the list.
unsigned int nth_number_of_k_setbit(unsigned int k, unsigned n)
{
unsigned initial = 1,i ;
for (i = 0; i < (k-1); i += 1)
initial = (initial<<1) | (1);
for (i = 0; i < n-1; i += 1)
initial = next_number( initial);
return initial;
}
int main()
{
cout<<"enter the value of k"<<endl;
unsigned k;
cin>>k;
cout<<"enter the value of n"<<endl;
unsigned n;
cin>>n;
cout.setf(ios::hex, ios::basefield);
cout<<"nth number of the increasing order of k-bit set list
is:"<<nth_number_of_k_setbit(k,n);
cout<<endl;
return 0;
}
hope this should help you.
--
Ashish Gupta
Ph. no. +91 9795 531 047
On Thu, Aug 27, 2009 at 10:35 PM, ankur aggarwal
<[email protected]>wrote:
> @shishir
>
> plz give an example..
> its bit tough to understand for me atleast..
>
>
> On Thu, Aug 27, 2009 at 6:10 PM, Shishir Mittal <[email protected]>wrote:
>
>> Its a bit similar to finding the rank of the word "COMPUTER" in the
>> dictionary among the words formed from C,O,M,P,U,T,E,R.
>>
>> Find maximum r such that (k+r)C(r) < n.
>> This represents the total number of numbers formed from 'r' 0 bits and 'k'
>> 1 bits. Since n is greater, it implies it has an extra 1 bit in its
>> representation.
>> The problem reduces to finding [n - (m+r)C(r)] smallest number than can be
>> formed with (k-1) 1 bits.
>>
>> here is a recursive function to obtain the result.
>> int rec(int curr, int n, int k){
>> int r,j,comb,tmp;
>> if(n==1)
>> return curr+((1<<k) - 1); /* 1st number in the sequence with m bits.
>> */
>> for(r =1,comb = 1; ; r++)
>> {
>> tmp = (comb*(k+r))/r; /* k+rCr = (k+r-1)C(r-1) x (k+r)/r */
>> if(tmp == n)
>> return curr + (1<<(k+r)) - (1<<r); /* All the 'k' left most bits
>> should be 1 and rest 0 */
>> else if(tmp > n)
>> return rec(curr+(1<<(k+r-1)), n-comb,k-1);
>> comb= tmp;
>> }
>> }
>>
>> Call rec(0,n,k) to get the nth number of the series with 'k' bits set.
>>
>>
>> On Thu, Aug 27, 2009 at 12:28 PM, ankur aggarwal <
>> [email protected]> wrote:
>>
>>>
>>> Nth number with K set bits
>>> We are given with k number of set bits (bit=1). We have to find the Nth
>>> number which has k set bits.
>>>
>>> for example
>>>
>>> k=3
>>>
>>> the numbers with k set bits are as follows:
>>>
>>> 000111 = 7
>>> 001011 = 11
>>> 001101 = 13
>>> 001110 = 14
>>> 010011 = 19
>>> 010101 = 21
>>> 010110 = 22
>>> 011001 = 25
>>> 011010 = 26
>>> 011100 = 28
>>> ....
>>> and so on....
>>>
>>> we have to find the Nth number in this series...
>>>
>>> suggest some method
>>>
>>>
>>>
>>
>>
>> --
>> Shishir Mittal
>> Ph: +91 9936 180 121
>>
>>
>>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
