https://leetcode.com/problems/complement-of-base-10-integer/
https://leetcode.com/problems/complement-of-base-10-integer/discuss/256740/JavaC%2B%2BPython-Find-111.....1111-greater-N
Then
https://leetcode.com/problems/complement-of-base-10-integer/discuss/256770/JavaPython-1-line-cheat
Every non-negative integer
N
has a binary representation. For example, 5
can be represented as "101"
in binary, 11
as "1011"
in binary, and so on. Note that except for N = 0
, there are no leading zeroes in any binary representation.
The complement of a binary representation is the number in binary you get when changing every
1
to a 0
and 0
to a 1
. For example, the complement of "101"
in binary is "010"
in binary.
For a given number
N
in base-10, return the complement of it's binary representation as a base-10 integer.
Example 1:
Input: 5 Output: 2 Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.
Example 2:
Input: 7 Output: 0 Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.
Example 3:
Input: 10 Output: 5 Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.
Note:
0 <= N < 10^9
https://leetcode.com/problems/complement-of-base-10-integer/discuss/256740/JavaC%2B%2BPython-Find-111.....1111-greater-N
O(logN)
Time
Let's find the first number
And also, it has to be noticed that,
X
that X = 1111....1 >= N
And also, it has to be noticed that,
N = 0
is a corner case expecting1
as result.Solution 1:
N + bitwiseComplement(N) = 11....11 = X
Then
bitwiseComplement(N) = X - N
public int bitwiseComplement(int N) {
int X = 1;
while (N > X) X = X * 2 + 1;
return X - N;
}
N ^ bitwiseComplement(N) = 11....11 = X
bitwiseComplement(N) = N ^ X
public int bitwiseComplement(int N) {
int X = 1;
while (N > X) X = X * 2 + 1;
return N ^ X;
}
public int bitwiseComplement(int n) {
return n != 0 ? n ^ (Integer.highestOneBit(n) << 1) - 1 : 1;
}
https://leetcode.com/problems/complement-of-base-10-integer/discuss/256741/Simple-Java-Sol-(XOR) public int bitwiseComplement(int N) {
// Find number of bits in the given integer
int bitCount = (int) Math.floor(Math.log(N)/Math.log(2))+1;
// XOR the given integer with math.pow(2,bitCount-1)
return ((1 << bitCount) - 1) ^ N;
}
https://leetcode.com/problems/complement-of-base-10-integer/discuss/257022/Java-simple-1-line-bit-manipulation-(left-and-right-shifts)-0ms
Just actually do the complement operation ~, after first shifting away all the leading zeroes, and then shift away all the trailing ones.
public int bitwiseComplement(int N) {
return (N==0) ? 1 : (~(N<<(N=Integer.numberOfLeadingZeros(N))))>>N;
}
X.https://leetcode.com/problems/complement-of-base-10-integer/discuss/256770/JavaPython-1-line-cheat
Swap 0 and 1 in the binary string.
public int bitwiseComplement(int N) {
return Integer.parseInt(Integer.toBinaryString(N).replace('0', '2').replace('1', '0').replace('2', '1'), 2);
}