ビット演算が文字列演算よりも遅い理由LeetCode＃476

Question

私は整数の補数整数を出力するように求めるleetCode質問を書いています。 LeetCode#476

私はいつもビット操作が速いと考えました。最後はビット操作ですべてが行われるからです。しかし、この問題では、文字列メソッドはビット操作よりも高速で、なぜ私は不思議に思っています。

11msで受け付けられる文字列操作コードを書きました。コードは、非常に直感的な、次のとおりです。

class Solution { 
    public int findComplement(int num) { 
     String s = Integer.toBinaryString(num); 
     StringBuilder sb = new StringBuilder(); 
     for(char c : s.toCharArray()){ 
      sb.append(c == '1' ? 0 : 1); 
     } 
     int ret = Integer.parseInt(sb.toString(), 2); 
     return ret; 
    } 
} 

問題を解決するためにビット操作を見つけて試しました。しかし、それは13msで受け入れられました。以下はコードです。

class Solution { 
    public int findComplement(int num) { 
     return ~num & ((Integer.highestOneBit(num) << 1) - 1); 
    } 
} 

Answer 1

私はLeetCodeのタイミングが少し疑わしいと確信しています。

まず、ビット操作ソリューションを複数回提出し、11〜14msの時間を得ました。 20回の反復が10回の未満の反復を取ったこと、

Number of iterations  Time/ms 
--------------------  ------- 
        1  11 
        10  17 
        20  14 
       200  32 
       20000  39 
      2000000  145 

注意、特に：

public int findComplement(int num) { 
    int ret = 0; 
    for (int i = 1; i <= 2000000; i++) 
     ret |= ~num & ((Integer.highestOneBit(num) << 1) - 1); 
    return ret; 
} 

結果：

Iは、次いで、反復の異なる数で、次のコードの様々なバージョンを提出しました。しかし、全体的に、反復に対する時間の上昇傾向があります。私はLeetCodeがメソッドを呼び出して意味のあるタイミングをとるのに十分な時間はないと思う。上記は、前の145ミリ秒に対して良好比較、2000000回の反復のために130ミリ秒を要し

public int findComplement(int num) { 
    int usedBits = num; 
    usedBits |= usedBits >> 1; 
    usedBits |= usedBits >> 2; 
    usedBits |= usedBits >> 4; 
    usedBits |= usedBits >> 8; 
    usedBits |= usedBits >> 16; 
    return ~num & usedBits; 
} 

：ここ

も速い方法です。

今度は、あなたのStringBuilderのメソッドを使用しての繰り返しをやってみましょう：

public int findComplement(int num) { 
    int ret = 0; 
    for (int i = 1; i <= 20000; i++) { 
     String s = Integer.toBinaryString(num); 
     StringBuilder sb = new StringBuilder(); 
     for(char c : s.toCharArray()){ 
      sb.append(c == '1' ? 0 : 1); 
     } 
     ret |= Integer.parseInt(sb.toString(), 2); 
    } 
    return ret; 
} 

時間：（ビット操作ソリューションのための37ミリ秒に対して）785ミリ