CodeSprint 2の補完チャレンジが遅すぎる

Question

元のInterviewStreet Codesprintには、aとbの間の2の補数表示の1の数を数えることに関する質問があります。私は繰り返しを使ってすべてのテストケースを正確に渡すことができましたが、正しい時間内に2つしか渡すことができませんでした。再発関係を見つけることについてのヒントがありましたので、再帰に切り替わりましたが、同じ時間がかかりました。だから誰も私が提供したコードよりこれを行うためのより速い方法を見つけることができますか？入力ファイルの最初の数は、ファイル内のテストケースです。コードの後ろにサンプル入力ファイルを用意しました。

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

を交換することですビット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 
} 

は、合計13の非常に安価な命令のために、4つのシフト、5つのビットごとのアンド、1つの減算、2つの加算および1つの乗算を使用する。

しかし、範囲が非常に小さい場合を除いて、を個々の数値のビット数よりも優れています。

最初に非負の数値を考えてみましょう。 0〜2の数字は、kビットが設定されています。^k -1すべてのビットはこれらのちょうど半分に設定されているので、合計ビット数は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ビットのセットを有し、先頭ビットを無視し、これらのビットはそう、

totalBits(a) = k*2^(k-1) + (a - 2^k + 1) + totalBits(a - 2^k) 

番号0 <= n <= (a - 2^k)と同じです今負の数です。 2の補数では-(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); 
}