[Swift]LeetCode476.数字的补数|NumberComplement

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10347716.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

Note:

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

给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

注意:

给定的整数保证在32位带符号整数的范围内。
你可以假定二进制数不包含前导零位。

示例 1:

输入: 5
输出: 2
解释: 5的二进制表示为101（没有前导零位），其补数为010。所以你需要输出2。

示例 2:

输入: 1
输出: 0
解释: 1的二进制表示为1（没有前导零位），其补数为0。所以你需要输出0。

Runtime: 8 ms

Memory Usage: 3.8 MB

1 class Solution {
2     func findComplement(_ num: Int) -> Int {
3         return (1 - num % 2) + 2 * (num <= 1 ? 0 : findComplement(num / 2))
4     }
5 }

Runtime: 8 ms

Memory Usage: 3.8 MB

 1 class Solution {
 2     func findComplement(_ num: Int) -> Int {
 3         var mask:Int = Int.max
 4         while ((mask & num) != 0)
 5         {
 6             mask <<= 1
 7         }
 8         return ~mask & ~num
 9     }
10 }

8ms

 1 class Solution {
 2     func findComplement(_ num: Int) -> Int {
 3     var numberOfBitsNeeded = 0
 4     var number = num
 5     while number > 0 {
 6         number /= 2
 7         numberOfBitsNeeded += 1
 8     }
 9     
10     
11     let allOnes = (2 << (numberOfBitsNeeded - 1)) - 1
12     
13     
14     return (num ^ allOnes)
15     }
16 }

3842 kb

1 class Solution {
2     func findComplement(_ num: Int) -> Int {
3         let numberOfBits = (String(num,radix:2)).count
4         return ((1 << numberOfBits) - 1) ^ num
5     }
6 }

3858 kb

 1 class Solution {
 2     func findComplement(_ num: Int) -> Int {
 3         
 4         let bitCount = num.bitWidth - num.leadingZeroBitCount
 5         
 6         var mask = 1
 7         
 8         for _ in 0..<bitCount - 1 {
 9             mask = mask << 1 + 1
10         }
11         
12         return num ^ mask
13     }
14 }

16ms

 1 class Solution {
 2     func findComplement(_ b: Int) -> Int {
 3         var count = 0
 4         var sum = 0
 5         while sum <= b {
 6             count += 1
 7             sum = 1 << count
 8         }
 9         
10         let rtn = sum - 1 - b
11         return rtn
12     }
13 }

28ms

 1 class Solution {
 2     func findComplement(_ num: Int) -> Int {
 3         var num = num
 4         var res = 0
 5         var offset = 0
 6 
 7         while num > 0 {
 8             res = res + ((num & 1) ^ 1) << offset
 9             num = num >> 1
10             offset += 1
11         }
12 
13         return res
14     }
15 }