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

其中浮現於日誌的深度一個，具有更快的實現中，例如著名的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 
} 

它使用四個班次，五個按位和，一個減法，兩個加法和一個乘法共十三個非常便宜的指令。

但是，除非範圍非常小，否則可以比計算每個單獨數字的位更好地執行更多。

讓我們先考慮非負數。從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 ^ķ位組，並忽略引導位，這些位是一樣的數字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); 
}