未分類

Number Complement

Go, LeetCode

Number Complement

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:

1
2
3
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:

1
2
3
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.

Default:

1
2
3
func findComplement(num int) int {
}

解答思路:

看到題目應該第一個想到的會是直接做NOT，不過別忘了前頭的至多個位元0也會跟著改變，不曉得為什麼Go在設計上並沒有~這個Not的運算子，倒是有AND NOT: &^，不過就算如此我們還是可以想出其它方案來處理，好比說就用XOR這個運算子^，如果5為101，我們要的結果是2(010)，那麼只要把5與7(111)做XOR即可，所以只要找出給予數字在二進制的長度，並且算出該長度位元皆為1時值為多少，最後兩者做XOR就會是我們要的結果。

程式碼解說:

一開始先找出給予值在二進位的長度，接著便以此長度開始迴圈累加計算(1,2,4,8…)相同長度的情況下，位元皆為1時值為多少，最後將累加的結果值與題目給予值做XOR就會是答案

1
2
3
4
5
6
7
var sum int
binary := 1
for i := 1; i <= len(strconv.FormatInt(int64(num), 2)); i++ {
	sum += binary
	binary *= 2
}
return sum ^ num

完整程式碼:

1
2
3
4
5
6
7
8
9
func findComplement(num int) int {
	var sum int
	binary := 1
	for i := 1; i <= len(strconv.FormatInt(int64(num), 2)); i++ {
		sum += binary
		binary *= 2
	}
	return sum ^ num
}

總結:

若有一數5(101)，題目要將其0變為1，所以結果為2(010)，在用not之前別忘了二進制32位元int先前存在著至多個位元0也會變化，除了可以用找出mask的方式再來處理之外，只用XOR來想辦法也是一種方案，找出給予數字在二進制的長度，並且算出該長度位元皆為1時值為多少，最後兩者做XOR就是結果。

分享到