java我们怎么能在一定的范围内，最大次数，一个整数可以被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

执行时间到了。执行时间超过16000毫秒

然后我试着只存储最容易被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表示为

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也可以

Answer 2

strongness实际上是数字二进制表示中尾随的零的数量。你可以用java.lang.Integer.numberOfTrailingZeros来获得它

当你想测试偶数时，你可以跳过循环中的奇数

public class StrongestEvenNumber {

  public static int strongestEven(int n, int m) {
    int maxStrongness = 0, maxNumber = 0;
    for(int i = n%2==0?n:n+1, strongness = 0; i <= m; i=i+2){
    strongness = Integer.numberOfTrailingZeros(i);
      if(strongness > maxStrongness){
        maxStrongness = strongness;
        maxNumber = i;
      }
    }
      return maxNumber;
  }

这将在分配的时间内运行：

Completed in 13190ms