unsigned next_number( unsigned x)
{
unsigned smallest, ripple, one;
(1)smallest = x & (-x);
(2)ripple = x + smallest ;
(3)one = ripple^x;
(4)one = (one>>2)/smallest;
(5) return ripple | one ;
}
let x is a given number in which (let say ) k bits are set. Now our aim to
find next big number while keeping no. of set bits equal to k.
Explanation:- let say here we take a x = aaa0 1111 0000 as an example. a
may be anything which is previously in the given number. Now result of the
next_number function should be
x = aaa1 0000 0111
(1) smallest = x& (-x) ; smallest contains the rightmost set bit, any other
bit is 0.
smallest = aaa0 0001 0000
(2) ripple = x + smallest ; ripple = aaa1 0000 0000 ( now one bit of the
result is in the ripple. we have to bring remaining 3 bit somehow in the
right adjusted position.
(3)one = ripple^x; // one = 0001 1111 0000
(4) one= one/smallest ; one = 0000 0001 1111
( dividing one by smallest will generate all the 1's bit at the right most
position . but this number will keep two 1's more than required. hence right
shift one by 2 position .
one = one>>2;
( 5) now OR this number with ripple and you will get the answer.
Hope this explanation should work.
On Fri, Sep 11, 2009 at 7:14 PM, amarnath ..... <[email protected]> wrote:
> 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
-~----------~----~----~----~------~----~------~--~---
