在原始InterviewStreet Codesprint上，有一个问题是要对a和b(含)之间的数字的补数表示形式中的个数进行计数。我能够使用迭代传递所有测试用例，以确保准确性，但我只能在正确的时间内传递两个。有提示提到要找到一个递归关系，所以我切换到递归，但最终花费了相同的时间。因此，有谁能找到比我提供的代码更快的方法？输入文件的第一个数字是文件中的测试用例。在代码之后，我提供了一个示例输入文件。
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
最佳答案
第一步是更换
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);
}
它以更快的实现方式递归到log2 a的深度，例如著名的位旋转
public static int popCount(int n) {
// count the set bits in each bit-pair
// 11 -> 10, 10 -> 01, 0* -> 0*
n -= (n >>> 1) & 0x55555555;
// count bits in each nibble
n = ((n >>> 2) & 0x33333333) + (n & 0x33333333);
// count bits in each byte
n = ((n >> 4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F);
// accumulate the counts in the highest byte and shift
return (0x01010101 * n) >> 24;
// Java guarantees wrap-around, so we can use int here,
// in C, one would need to use unsigned or a 64-bit type
// to avoid undefined behaviour
}
它使用四个移位，五个按位与，一个减法，两个加法和一个乘法，总共13条非常便宜的指令。
但是除非范围很小，否则比对每个数字的位数进行计数，可以更好地实现。
让我们首先考虑非负数。从0到2k-1的数字都最多设置了
k位。每个位正好设置为其中的一半，因此位的总数为k*2^(k-1)。现在让2^k <= a < 2^(k+1)。数字0 <= n <= a中的位数总数是数字0 <= n < 2^k中的位数与数字2^k <= n <= a中的位数的总和。如上文所述，第一个计数是k*2^(k-1)。在第二部分中，我们有a - 2^k + 1数字，每个数字都有2k位设置，并且忽略了前导位，这些数字的位与0 <= n <= (a - 2^k)中的数字相同，因此totalBits(a) = k*2^(k-1) + (a - 2^k + 1) + totalBits(a - 2^k)
现在为负数。在二进制补码
-(n+1) = ~n中，因此数字-a <= n <= -1是数字0 <= m <= (a-1)的补码，数字-a <= n <= -1中的置位总数为a*32 - totalBits(a-1)。对于
a <= n <= b范围内的总位数，我们必须加或减，具体取决于范围的两端是相反符号还是相同符号。// if n >= 0, return the total of set bits for
// the numbers 0 <= k <= n
// if n < 0, return the total of set bits for
// the numbers n <= k <= -1
public static long totalBits(int n){
if (n < 0) {
long a = -(long)n;
return (a*32 - totalBits((int)(a-1)));
}
if (n < 3) return n;
int lg = 0, mask = n;
// find the highest set bit in n and its position
while(mask > 1){
++lg;
mask >>= 1;
}
mask = 1 << lg;
// total bit count for 0 <= k < 2^lg
long total = 1L << lg-1;
total *= lg;
// add number of 2^lg bits
total += n+1-mask;
// add number of other bits for 2^lg <= k <= n
total += totalBits(n-mask);
return total;
}
// return total set bits for the numbers a <= n <= b
public static long totalBits(int a, int b) {
if (b < a) throw new IllegalArgumentException("Invalid range");
if (a == b) return popCount(a);
if (b == 0) return totalBits(a);
if (b < 0) return totalBits(a) - totalBits(b+1);
if (a == 0) return totalBits(b);
if (a > 0) return totalBits(b) - totalBits(a-1);
// Now a < 0 < b
return totalBits(a) + totalBits(b);
}