Прежде всего, ваш вопрос не является корректным.Это пример того, как не следует задавать вопрос (без обид).Я возьму, что ваш вопрос таков: если задано положительное целое число x, найдите такие целые числа m, n, что x = m * 2 ^ n, где m нечетно, затем верните y = f (x) = n + g (m).Поскольку вы не указали, как вычисляется f (x) для нечетного x, я предполагаю, что g (.) Задано.
Если в вашей задаче n не велико, использование большегосложный алгоритм, чем простой цикл (наивный алгоритм).Я представлю алгоритм, который полезен для случая, когда n велико (скажем, несколько сотен, несколько тысяч).Я не знаю Java, поэтому я представляю алгоритм в общем виде (используя синтаксис в стиле Python).
Если вы берете двоичное представление x (b_ {N-1} ... b_1 b_0, b_i = 0 или 1), тогда ваша проблема сводится к нахождению первого бита 1 справа (т.е. младшего значащего бита 1).Скажем, позиция этого бита k (0 <= k <= N-1), тогда n = k и m = x >> k.Я считаю, что лучшее, что вы можете сделать, чтобы найти k, это использовать бинарный поиск, который приводит к алгоритму O (log N).Алгоритм выглядит следующим образом (<< и >> - операторы сдвига):
Algorithm: Input: x -> Outputs: (m, n)
if x is odd or x == 0: return (x, 0) # x is odd when x & 1 == 1 or x % 2 == 1
N = ceil(log(x, 2)) # ceil: smallest integer larger than the argument
n = 0
orig_x = x
while x & 1 == 0: # if bit 0 is 1 (i.e. x is odd), stop the search
half = int(N/2)
lowerhalf = x & ((1 << half) - 1) # obtain the lower half
if lowerhalf == 0: # all zeros
n += half
x = x >> half
N -= half
else:
x = lowerhalf
N = half
return (orig_x >> n, n)
Например, если N = 1000 (x - 1000-битное целое число), этот алгоритм занимает не более 10 итераций.(в то время как наивный алгоритм требует 1000 итераций в худшем случае).Однако фактическое время выполнения зависит от того, как реализованы битовые операции и оператор == для целых чисел длиной 1000 бит.