Problem

Problem_Link

Solutions (time, space)

1. bit calculation with JAVA method
2. bit calculation with bitwise operator

I solved with JAVA method. But, this problem is asking, "Do you know bitwise? Do you know how computer save data?"

bit calculation with JAVA method O(n), O(n)

class Solution {
    public int bitwiseComplement(int n) {
        String base2String = Integer.toBinaryString(n);
        StringBuilder sb = new StringBuilder(base2String.length());

        for (char tempChar : base2String.toCharArray()) {
            int tempInt = (tempChar == '1') ? 0 : 1;
            sb.append(tempInt);
        }

        return Integer.parseInt(sb.toString(), 2);
    }
}

Explanation

1. get base 2 String from input int base 10
2. reverse the base 2 String by StringBuilder
3. get base 10 in from reversed base 2 String

bit calculation with bitwise operator O(n), O(1)

class Solution {
    public int bitwiseComplement(int n) {
        int bitCounter = n;
        int tempBit = 0;

        if (n==0) return 1;

        while (bitCounter != 0) {
            tempBit = (tempBit << 1) | 1;
            bitCounter = bitCounter >> 1;
        }

        return (~n & tempBit);
    }
}

Explanation

1. ~10 (NOT gate of n) = 1111 1111 1111 1111 1111 1111 1111 0101 (because of Java using 32 bits)
2. ~10 & 1111 = the answer=0101
3. to get 1111, move bit to left and add 1 only length what we wanted.
4. bitCounter : the length of bits for input
5. tempBit : added 1 as length

         while (bitCounter != 0) {
             tempBit = (tempBit << 1) | 1;
             bitCounter = bitCounter >> 1;
         }