Why Bit Operation is slower than String Operation LeetCode#476

Question

I am writing a leetCode question where ask me to output a integer's complement integer. LeetCode#476

I always thought bit manipulation is fast because in the very end, everything is done by bit manipulation. But in this problem, a string method is faster than bit manipulation and I am wondering why.

I wrote a string operation code which is accepted in 11ms. The code is following, very intuitive.

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

I peeked through the discussions and found a bit operation to solve the problem and I tried it. However, it was accepted with 13ms. Below is the code.

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

Well, you are not just manipulating bits: I don't know if it has any impact on performance, but `highestOneBit` does a subtraction and you do a subtraction too (`((Integer.highestOneBit(num) << 1) - 1)`. That *may* slow down the process (but I'm not sure.) — BackSlash, Dec 11 '17 at 18:14
[How do I write a correct micro-benchmark in Java?](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) — Oliver Charlesworth, Dec 11 '17 at 18:15
Start by [writing a proper benchmark](https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java). The fact that there's a 2 ms difference here doesn't say much at all about which one's actually faster in general. — Bernhard Barker, Dec 11 '17 at 18:16
What do you mean by "accepted in X ms"? Is this your own timing, or did LeetCode report the time? — DodgyCodeException, Dec 11 '17 at 18:20
If the timings are something LeetCode gave you, they are probably completely meaningless. The vast majority of the time spent running such a small program will be spent doing things like loading classes. Also, [based on how LeetCode's answers are given](https://leetcode.com/problems/number-complement/description/), I bet they are using reflection to call the method which means the API needs to do some really heavy-weight stuff, like synthesize the bytecode for an accessor proxy class. — Radiodef, Dec 11 '17 at 18:26
The actual time something like that would cost is a couple of nanoseconds, everything else is overhead. — harold, Dec 11 '17 at 18:37
I thought most of these sites compiled your code and called your method it in a loop for several thousand (or million) iterations and gave the timing for that many iterations (hence ms rather than ns). Perhaps your string version was in ms while the bit-manipulation version was in μs? — DodgyCodeException, Dec 11 '17 at 18:41

DodgyCodeException · Answer 1 · 2017-12-12T11:04:02.677

I'm certain that LeetCode's timings are a bit suspect.

First, I submitted the bit-manipulation solution several times and got times varying from 11 to 14 ms.

I then submitted various versions of the following code, with differing numbers of iterations:

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

The results:

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

Notice, in particular, that 20 iterations took less than 10 iterations. But overall, there is an upward trend of time versus iterations. I think LeetCode is not calling the method enough times to do any meaningful timings.

Here's an even faster method:

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

The above takes 130 ms for 2000000 iterations, comparing favourably against the previous 145 ms.

Now let's try doing iterations using your StringBuilder method:

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

Time: 785 ms (against 37 ms for the bit-manipulation solution)

Why Bit Operation is slower than String Operation LeetCode#476

1 Answers1