Algorithms to Compute the Bitwise AND of Numbers in a Range
- 时间:2020-10-11 15:25:20
- 分类:网络文摘
- 阅读:139 次
Given a range [m, n] where 0 <= m <= n <= 2147483647 (32 bit), return the bitwise AND of all numbers in this range, inclusive.
Example 1:
Input: [5,7]
Output: 4Example 2:
Input: [0,1]
Output: 0
Bruteforce Algorithm to Compute the Bitwise AND of numbers within a range
The most intutuive solution is to apply the Bitwise AND for each numbers in a range, and the complexity will be O(N) where N is the total of the integers between M and N.
1 2 3 4 5 6 7 8 9 10 | class Solution { public: int rangeBitwiseAnd(int m, int n) { int res = m; for (int i = m + 1; i <= n; ++ i) { res &= i; } return res; } }; |
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int res = m;
for (int i = m + 1; i <= n; ++ i) {
res &= i;
}
return res;
}
};For inputs such as (0, 2147483647), the above bruteforce algorithm is inefficient to give a answer as all the numbers are iterated.
Compute the Common Prefix in Binary
Let’s take the numbers from 4 to 7 in binary, and do a bitwise AND.
0100
0101
0110
0111
The common prefix is 01, which converted to binary is 4. Thus, we can find the common prefix of all numbers between m and n using the following O(1) algorithm (both constant in time and space).
While m is smaller than n, we shift both numbers one position to the right (effectively dividing both numbers to two).
m = 0100, n = 0111, shift = 0
m = 0010, n = 0011, shift = 1
m = 0001, n = 0001, shift = 2
Thus, the answer is 1 << 2 = 0100
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: int rangeBitwiseAnd(int m, int n) { int shift = 0; while (m < n) { m >>= 1; n >>= 1; shift ++; } return m << shift; } }; |
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int shift = 0;
while (m < n) {
m >>= 1;
n >>= 1;
shift ++;
}
return m << shift;
}
};Another solution is to clear the rightmost 1 bit of n (apply the trick), until it is smaller or equal to m.
1 2 3 4 5 6 7 8 9 | class Solution { public: int rangeBitwiseAnd(int m, int n) { while (m < n) { n = n & (n - 1); } return m & n; } }; |
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
while (m < n) {
n = n & (n - 1);
}
return m & n;
}
};This approach is also O(1) in both time and space. This puzzle is one of those classic ones where we could apply those smart bit tweaks (twicks).
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:How to Design Underground System using Several Hash Maps? How to Remove Zero Sum Consecutive Nodes from Linked List using Depth First Search and Breadth First Search Algorithm to Open th Dynamic Programming (Memoization) to Sort Integers by The Power Applicable Accounting Software For Churches How to Balance a Binary Search Tree using Recursive Inorder Trav Finding the Lucky Numbers in a Matrix Factory Design Pattern in Object Oriented Design Programming Algorithm to Find Minimum Removals to Make Valid Parentheses Greedy Algorithm to Validate Stack Sequences
- 评论列表
-
- 添加评论