can u please explain me the logic behind finding the next number?
On Fri, Sep 11, 2009 at 1:42 AM, ashish gupta <[email protected]>wrote:
> 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
-~----------~----~----~----~------~----~------~--~---
