for example from 12 to 14 the highest power of 2 that divides is 2^2 that divides 12.
this can be done by factoring all numbers from n to m in form 2^k * l and then finding the highest k however that can be a very slow process. and this can be improved signifcantly
let n = 2^p * q where q is odd( p = 0 in case n is odd)
next multiple of 2^p shall be n + 2^p
so we have algorithm
let n = 2 ^p* q
set r = 2 ^ p + q (1st number)
loop step:
if r + 2^p > m exit
add 2 ^p to r and 1 to q( r = r + 2^p , q = q + 1)
keep deviding q by 2 adding 1 to p until q is odd
go to loop step:
r is the value and p is the highest power
suppose we need to find between 21 and 31
21 = 2^0 * 21
add 1 22 = 2 ^ 0 * 22 or 2^1 * 11
add 2^1 or 2, 24 = 2^1 * 12 or 2^3 *3
add 2^3 or 8 we get 32 > 31
so and = 24 = 2^3 * 3
No comments:
Post a Comment