[Swift]LeetCode201.数字范围按位与|BitwiseANDofNumbersRange

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

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

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

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

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

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

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: [5,7]
Output: 4

Example 2:

Input: [0,1]
Output: 0

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

示例 1:

输入: [5,7]
输出: 4

示例 2:

输入: [0,1]
输出: 0

44ms

 1 class Solution {
 2     func topDigit(_ n: Int) -> Int {
 3         var n = n
 4         while (n & (n-1)) != 0 {
 5             n = (n & (n-1))
 6         }
 7         return n
 8     }
 9     func rangeBitwiseAnd(_ m: Int, _ n: Int) -> Int {
10         guard m > 0 && n > 0 else {
11             return 0
12         }
13         var m2 = topDigit(m)
14         var n2 = topDigit(n)
15         
16         if n2 != m2 {
17             return 0
18         }
19         
20         return m2 | rangeBitwiseAnd(m-m2, n-m2)
21     }
22 }

48ms

 1 class Solution {
 2     func rangeBitwiseAnd(_ m: Int, _ n: Int) -> Int {
 3         if m == 0 {
 4             return 0
 5         }
 6         
 7         var m = m
 8         var n = n
 9         var factor = 1
10         
11         while m != n {
12             m >>= 1
13             n >>= 1
14             factor <<= 1
15         }
16         
17         return m * factor
18     }
19 }

52ms

 1 class Solution {
 2     func rangeBitwiseAnd(_ m: Int, _ n: Int) -> Int {
 3         /*
 4         0  - 0000
 5         1  - 0001
 6         2  - 0010
 7         3  - 0011
 8         4  - 0100
 9         5  - 0101
10         6  - 0110
11         7  - 0111
12         8  - 1000
13         9  - 1001
14         10 - 1010
15         
16         8..10  =>  1000
17         */
18 
19         var m = m
20         var n = n
21         var i = 0
22         while m != n {
23             m >>= 1
24             n >>= 1
25             i += 1
26         }
27         return m << i
28     }
29 }

52ms

1 class Solution {
2     func rangeBitwiseAnd(_ m: Int, _ n: Int) -> Int {
3         return (n > m) ? (rangeBitwiseAnd(m / 2, n / 2) << 1) : m
4 
5     }
6 }

56ms

 1 class Solution {
 2     func rangeBitwiseAnd(_ m: Int, _ n: Int) -> Int {
 3         var plus = 1
 4         var result = m & n
 5         while m + plus < n {
 6             result &= m + plus
 7             plus += plus
 8         }
 9         return result
10     }
11 }

64ms

 1 class Solution {
 2     func rangeBitwiseAnd(_ m: Int, _ n: Int) -> Int {
 3         // 101011101
 4         // 101111001
 5         
 6         var m = m
 7         var n = n
 8         var res = 0
 9         var t = 1
10         for i in 0..<31 {
11             if m % 2 == 0 || n % 2 == 0 || m < n {
12                 m = m >> 1
13                 n = n >> 1
14             } else {
15                 res += t
16                 m = m >> 1
17                 n = n >> 1
18             }
19             
20             t *= 2
21         }
22         
23         return res
24     }
25 }