怎么才能在一定范围内，最大次数，一个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();
  }
}

但是，如果数字很大，它会用完堆内存 space，或者执行时间用完。例如：

n: 1180381085
m: 2074186600

Java 堆 space 用完了。

还有：

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;
  }
}

确实它解决了堆 space 困难，但是执行时间用完的行为仍然发生。

例如：

n: 200275492
m: 1590463313

执行时间超过16000毫秒

我也看过：

Finding Key associated with max Value in a Java Map
https://math.stackexchange.com/questions/2589831/how-many-times-can-i-divide-a-number-by-another
optimize code to get the number of integers within given range that are divisible by integer

Answer 1

嗯，当 x 表示为

时，值 x 的强度是 n

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

强度实际上是数字的二进制表示中尾随零的数量。您可以使用 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

怎么才能在一定范围内，最大次数，一个int能被2整除

How could we get within a certain range, the maximum number of times, an int is divisible by 2

java

algorithm

math

int

numbers