Actually, it doesn't do what the requester asked even when x is a power of
2, because, e.g., the output for n = 6 and x = 2 is 6, but according to the
examples provided, the output should be 8, the next higher multiple of 2.
You could use (n + x) & ~(x-1) or (n + x) & (-x) for the x = power of two
case.
For general x > 0, the following algorithm is O(log n):
int nextLargerMultiple(int n, int x)
{
int r = n, d = x;
while( r <= d ) d <<= 1;
while( d != x )
{
d >>= 1;
if( r >= d ) r -= d;
}
return n - r + x;
}
Think long division, as you learned to do it with paper and pencil. The
first while loop shifts x left enough that the result is > n. The second
while loop successively shifts x right one place and if
possible subtracts it from n. At the end of the second while loop r is the
remainder; n%x. Subtracting r from n gives the n rounded down to a multiple
of x, and then adding x gives the next larger multiple of x.
Dave
On Thursday, September 13, 2012 9:03:49 AM UTC-5, bharat wrote:
>
> the above code works only for 2,4,8,16 ...
>
> On Thu, Sep 13, 2012 at 7:13 PM, VIHARRI P L V
> <[email protected]<javascript:>
> > wrote:
>
>> Let me give an example.
>>
>> For 17 next multiple of number 5 is 20.
>> For 20 next multiple of number 5 is 25.
>>
>> And give solution for this proeblem also:
>>
>> For 17 next nearest multiple of number 5 is 20.
>> For 20 next nearest multiple of number 5 is 20.
>>
>> *VIHARRI P L V*
>>
>>
>>
>>
>> On Thu, Sep 13, 2012 at 7:09 PM, bharat b
>> <[email protected]<javascript:>
>> > wrote:
>>
>>> @vihari: what is n?
>>>
>>> On Thu, Sep 13, 2012 at 6:32 PM, VIHARRI <[email protected]<javascript:>
>>> > wrote:
>>>
>>>> hey for finding next multiple of a number x using bitwise : ( n + x -1
>>>> ) & ~(x-1) but not working for all numbers
>>>> Could some one please explain me.
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To view this discussion on the web visit
>>>> https://groups.google.com/d/msg/algogeeks/-/7C_Nw4RoxmEJ.
>>>> To post to this group, send email to [email protected]<javascript:>
>>>> .
>>>> To unsubscribe from this group, send email to
>>>> [email protected] <javascript:>.
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>> --
>>> 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]<javascript:>
>>> .
>>> To unsubscribe from this group, send email to
>>> [email protected] <javascript:>.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> 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]<javascript:>
>> .
>> To unsubscribe from this group, send email to
>> [email protected] <javascript:>.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/e0LIWXHAQjMJ.
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?hl=en.
