在原始的InterviewStreet Codesprint上,有一个问题需要计算两个补码表示之间数字中1的数量。我通过迭代方式通过了所有精度测试用例,但只能在正确的时间内通过两个测试用例。有一个提示提到可以找到递推关系,所以我尝试使用递归,但最终它花费的时间与迭代相同。所以,是否有人可以找到比我提供的代码更快的方法?输入文件的第一个数是文件中测试用例的数目。我已经在代码后面提供了一个示例输入文件。
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int numCases = scanner.nextInt();
for (int i = 0; i < numCases; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
System.out.println(count(a, b));
}
}
/**
* Returns the number of ones between a and b inclusive
*/
public static int count(int a, int b) {
int count = 0;
for (int i = a; i <= b; i++) {
if (i < 0)
count += (32 - countOnes((-i) - 1, 0));
else
count += countOnes(i, 0);
}
return count;
}
/**
* Returns the number of ones in a
*/
public static int countOnes(int a, int count) {
if (a == 0)
return count;
if (a % 2 == 0)
return countOnes(a / 2, count);
else
return countOnes((a - 1) / 2, count + 1);
}
}
输入:
3
-2 0
-3 4
-1 4
Output:
63
99
37