java - 我们怎样才能得到在一定范围内，int能被2整除的最大次数

Question

我正在做以下编程练习:Strongest even number in an interval 。声明如下:

A strongness of an even number is the number of times we can successively divide by 2 until we reach an odd number starting with an even number n.

For example, if n = 12, then

12 / 2 = 6

6 / 2 = 3

we divided successively 2 times and we reached 3, so the strongness of 12 is 2.

If n = 16 then

16 / 2 = 8

8 / 2 = 4

4 / 2 = 2

2 / 2 = 1

we divided successively 4 times and we reached 1, so the strongness of 16 is 4 Task

Given a closed interval [n, m], return the even number that is the strongest in the interval. If multiple solutions exist return the smallest strongest even number.

Note that programs must run within the alloted server time; a naive solution will probably time out. Constraints

1 <= n < m <= INT_MAX Examples

for the input [1, 2] return 2 (1 has strongness 0, 2 has strongness 1)

for the input [5, 10] return 8 (5, 7, 9 have strongness 0; 6, 10 have strongness 1; 8 has strongness 2)

for the input [48, 56] return 48

首先，我想将每个数字作为键存储在映射中，并将其被 2 整除的次数作为值存储:

import java.util.*;

public class StrongestEvenNumber {
  public static int strongestEven/*💪*/(int n, int m) {
    System.out.println("n: "+n);
    System.out.println("m: "+m);
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();    
    for(int i = n, number = 0, strongness = 0; i <= m; i++){
      for(number = i, strongness = 0; number % 2 == 0; strongness++){
        number /= 2;
      }
      map.put(i, strongness);
    }
      Map.Entry<Integer, Integer> maxEntry = null;
      for(Map.Entry<Integer,Integer> entry : map.entrySet()){
        if(maxEntry == null || entry.getValue().compareTo(maxEntry.getValue()) > 0){
          maxEntry = entry;
        }
      }
      return maxEntry.getKey();
  }
}

但是，当数字很大时，它会耗尽堆内存空间，或者执行时间耗尽。例如:

n: 1180381085
m: 2074186600

Java 堆空间耗尽。

还有:

n: 324243
m: 897653214

执行时间耗尽。执行时间超过16000ms

然后我尝试只存储最常被 2 整除的数字:

import java.util.*;

public class StrongestEvenNumber {
  public static int strongestEven/*💪*/(int n, int m) {
    System.out.println("n: "+n);
    System.out.println("m: "+m);
    int maxStrongness = 0, maxNumber = 0;
    for(int i = n, number = 0, strongness = 0; i <= m; i++){
      for(number = i, strongness = 0; number % 2 == 0; strongness++){
        number /= 2;
      }
      if(strongness > maxStrongness){
        maxStrongness = strongness;
        maxNumber = i;
      }
    }
      return maxNumber;
  }
}

确实解决了堆空间问题，但是执行时间耗尽的行为仍然发生。

例如:

n: 200275492
m: 1590463313

执行时间超过16000毫秒

我还读过:

• Finding Key associated with max Value in a Java Map
• Get the key for the maximum value in a HashMap using Collections
• https://math.stackexchange.com/questions/2589831/how-many-times-can-i-divide-a-number-by-another
• Number of times all the numbers in an array are divisible by 2
• optimize code to get the number of integers within given range that are divisible by integer

Answer 1

那么，当 x 表示为

时，值 n 的强度就是 x

x = k * 2**n

知道了这一点，如果我们能找到任何 2 ，我们就可以检查 1, 2, 4, 8, ... (即 k )的所有权力

from <= k * 2**n <= to  

代码:

private static int strongestEven(int from, int to) {
  if (to < from)
    return -1; // Or throw exception

  // best power of 2 we can insert between [to..from] as k * best
  int best = 1;

  while (true) {
    int ceiling = from / best + (from % best == 0 ? 0 : 1);
    int floor = to / best;

    if (ceiling > floor) {
      best = best / 2;

      return best * (to / best);
    }

    best *= 2;
  }
}

测试:

  [ 1,   2] =>   2
  [ 5,  10] =>   8
  [48,  56] =>  48
  [80, 100] =>  96
  [97, 100] => 100

最后，

  [1180381085, 1590463313] => 1342177280

我们有 1342177280 == 5 * 268435456 == 5 * 2**28，因此 [1180381085, 1590463313] 范围内最强的数字具有强度 28

请注意，该算法具有 O(log(to)) 时间复杂度，这就是为什么即使我们将所有 int 转换为 long 也会这样做