[Swift]LeetCode201. 数字范围按位与 | Bitwise AND of Numbers

发布时间：2020-12-14 05:08:30 所属栏目：百科来源：网络整理

导读：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，返回此范围内所有

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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!