@Arun: Just think about doing long division with paper and pencil. The q<<=1 statement is the same as bringing down a new digit. Doing so also expands the quotient by one digit. The q|=1 statement is the same as writing down a nonzero digit in the quotient.
Dave On Aug 19, 10:31 am, Arun Vishwanathan <aaron.nar...@gmail.com> wrote: > @dave: actually how did u get the approach to this? I mean why did u have to > do the q|=1 in the if(a>=b) condition and q<<=1 always in the loop? > > On Fri, Aug 19, 2011 at 1:46 PM, Sanjay Rajpal > <tosanjayraj...@gmail.com>wrote: > > > > > > > @Shashank : Would you throw some light on how you determined the complexity > > ? > > > *Regards > > > Sanju > > > Happy to Help :)* > > > On Fri, Aug 19, 2011 at 2:36 AM, WgpShashank > > <shashank7andr...@gmail.com>wrote: > > >> We can use bit logic to reduce the time complexity to O(logn) where n is > >> Quotient > > >> Algorithm will be as follow as we know > > >> 1. Left shifting an unsigned number by 1 multiplies that number by 2. > >> 2. Right shifting an unsigned number by 1 divides that number by 2. > > >> Therefore the procedure for the division algorithm, given a dividend and a > >> divisor . > >> core logic will be to left shift (multiply by 2) untill its greater then > >> dividend , then continue this routine with the the difference between the > >> dividend and divisor and divisor till the point where dividend is less than > >> divisor or their difference is zero. > > >> Lets see one example: dividend=23 divisor=3 > > >> then left shift for 3 i.e 3 will converted to3, 6,12,24,… since 12 <23 > >> hence now dividend is 11 and quotient in 4(two time shift operation) now > >> again 3,6,12.. 6<11 hence dividend is 11-6=5 and quotient =4+2=6 now only > >> 3<5 hence remainder =2 quotient =6+1=7 so answer. > > >> Time Complexity O(logn) Number of bits in Quotient > > >> Correct me if anything wrong > > >> *Thanks > >> Shashank Mani > >> Computer Science > >> Birla Institute of Technology Mesra* > > >> -- > >> 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/-/VszScC-sOfoJ. > > >> To post to this group, send email to algogeeks@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. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@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. > > -- > "People often say that motivation doesn't last. Well, neither does bathing > - that's why we recommend it daily." -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
