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 <anandut2...@gmail.com> 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 <dave_and_da...@juno.com> 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 <sweetdivya....@gmail.com> 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 algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com<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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
