2018年1月31日 星期三

[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++(參考解法)

Java(參考解法)

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

沒有留言:

張貼留言