[LeetCode] 476. Number Complement

轉自LeetCode

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

Note:

1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
2. 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.

<Solution>

想法如下

num :  1101

mask:  11111111

因為 num 總共有四位，所以將 mask 左移四位，變成 11110000

然後將兩個都 flip

~num : 0010

~mask : 00001111

答案就會是 ~num & ~mask 了

code 如下

C++(參考解法)

	class Solution {
	public:
	int findComplement(int num) {
	unsigned int mark = ~0;
	//>> find the length of num
	while(mark & num) {
	mark <<= 1;
	}
	return ~mark & ~num;
	}
	};

view raw numberComplement.cpp hosted with ❤ by GitHub

Java(參考解法)

使用 Integer.highestOneBit 來找到 LMB，然後左移一位再減1，這樣就可以做出所要的 mask

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

view raw numberComplement.java hosted with ❤ by GitHub