как найти наименьшее количество операций для вычисления x ^ n

вот проблема из

ACM International Collegiate Чемпионат Азии по программированию Contest, Yokohama, 2006-11-05

Начиная с x и многократно умножая на x , мы можем вычислить x ^ 31 с тридцатью умножениями:

x^2 = x * x, x^3 = x^2 * x, x^6 = x^3 * x^3, x^7 = x^6 *x, x^14 = x^7 * x^7 ,
x^15 = x^14 * x, x^30 = x^15 * x^15 , x^31 = x^30 * x

напишите программу для найти наименьшее количество операций для вычисления x ^ n путем умножения и деления, начиная с x для данного положительного целого числа n и n <= 200

для n = 31 наименьшее количество операций равно 6
для n = 50 наименьшее количество операций - 7

Любые идеи приветствуются.