-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathBitwiseANDofNumbersRange.py
More file actions
80 lines (58 loc) · 2.02 KB
/
Copy pathBitwiseANDofNumbersRange.py
File metadata and controls
80 lines (58 loc) · 2.02 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
"""
https://leetcode.com/problems/bitwise-and-of-numbers-range/
Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.
Example 1:
Input: left = 5, right = 7
Output: 4
Example 2:
Input: left = 0, right = 0
Output: 0
Example 3:
Input: left = 1, right = 2147483647
Output: 0
Constraints:
0 <= left <= right <= 231 - 1
"""
from Common.ObjectTestingUtils import run_functional_tests
# class Solution:
# def rangeBitwiseAnd(self, left: int, right: int) -> int:
# # 101 110 111
# # 01..111 - 10..000
# result = 0
# for bit in range(32):
#
# return result
# Runtime: 60 ms, faster than 70.68% of Python3 online submissions for Bitwise AND of Numbers Range.
# Memory Usage: 14 MB, less than 99.62% of Python3 online submissions for Bitwise AND of Numbers Range.
# https://leetcode.com/problems/bitwise-and-of-numbers-range/discuss/1514191/Bit-mask-(Java)
# class Solution:
# def rangeBitwiseAnd(self, left: int, right: int) -> int:
# if left == right:
# return right
# mask = int(math.log2(right-left)) + 1
# return right & left >> mask << mask
# Runtime: 72 ms, faster than 40.97% of Python3 online submissions for Bitwise AND of Numbers Range.
# Memory Usage: 14.3 MB, less than 55.95% of Python3 online submissions for Bitwise AND of Numbers Range.
# https://leetcode.com/submissions/detail/348088723/
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
M, N = left, right
result = 0
mask = 1 << 31
while mask > M:
mask >>= 1
mask_c = 0
while mask:
mask_c |= (mask << 1)
if mask & M and mask & N:
x = (M & mask_c) + (mask << 1)
if x > N or x < M:
result |= mask
mask >>= 1
return result
tests = [
[5, 7, 4],
[0, 0, 0],
[1, 2147483647, 0]
]
run_functional_tests(Solution().rangeBitwiseAnd, tests)