In step 3, if n > m, then n can be written in the form i * 2^k + j, where i > 0 and 0 <= j <= m. Then, step 3 replaces n by i + j. Note that (i * 2^k + j) - (i + j) = i * (2^k - 1) = i * m. Therefore, the step replaces any number greater than m by a small number that differs from it by a multiple of m. Thus, if the original number is divisible by m, the sequence of smaller numbers produced by the algorithm will also be divisible by m, and conversely, if the original number is not divisible by m, the smaller numbers also will not be divisible by m.
Dave On Jun 23, 1:33 pm, Anand <[email protected]> wrote: > @Dave Logic is good. > could not understand how does it works. Could you please explain > > > > On Tue, Jun 22, 2010 at 9:16 PM, Dave <[email protected]> wrote: > > Let m = 2^k - 1. > > To check divisibility of n by m, > > 1. If n is zero, return true. > > 2. If n is negative, replace n with -n. > > 3. While n > m, replace n with (n >> k) + (n & m). > > 4. Return (n == m). > > > This is equivalent to the "casting out nines" algorithm to determine > > if a number is a multiple of 9. > > > Dave > > > On Jun 22, 3:37 pm, divya <[email protected]> wrote: > > > u are given any binary no...... u have to check its divisbility by > > > 3,7,15, > > > 31......(any no. of the form 2^x-1) > > > .u cant use any division > > > and modulo operator for that..... > > > -- > > 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]<algogeeks%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- 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?hl=en.
