java - CodeSprint 2 的补码挑战运行得太慢

Question

关于原文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

Answer 1

第一步是替换

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

递归到 log₂ a 的深度，具有更快的实现，例如著名的 bit-twiddling

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
}

它使用 4 次移位、5 次按位与、1 次减法、2 次加法和 1 次乘法，总共 13 条非常便宜的指令。

但除非范围非常小，否则与计算每个数字的位数相比，可以做得很多。

让我们首先考虑非负数。从 0 到 2^k-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数字，每个都有 2^k 位设置，忽略前导位，这些位与数字中的位相同 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);
}