NumberComplement [source code]

public class NumberComplement {
    public int findComplement(int num) {
        int count = 0;
        int number = num;
        while (number > 0) {
            number = number >> 1;
            count ++;
        }
        return num ^ (int)(Math.pow(2, count) - 1);
    }

    public static void main(String[] arg) {
        NumberComplement tester = new NumberComplement();
        Scanner reader = new Scanner(System.in);
        System.out.println("Type the input: ");
        System.out.println(tester.findComplement(reader.nextInt()));
    }
}

总体比较简单的一题,flip bits的思路的做法很直接,一个 xor 就可以了. 一开始的想法是直接跟0xFFFF xor,但是这个做法显然是有问题的,因为0000 0101前面的0也全被 flip 了.
所以要考虑先怎么得到 num 的 bit 长度. 这个也是一个很常规的问题. 得到了 count 之后,怎么得到全1?这个其实也很简单.

最后这个算法跑出来是43ms,应该不是特别好的,后面应该看看 discussion 学习更快的算法; 把一个 printf 删掉之后就是10ms 了;

Problem Description

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:
The given integer is guaranteed to fit within the range of a 32-bit signed integer.
You could assume no leading zero bit in the integer’s binary representation.
Example 1:
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Example 2:
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.
Bit Manipulation