Bitwise Manipulation
In this approach, bits are directly manipulated to compute the AND of numbers in the given range without using any additional data structures. It is based on observing patterns in the bitwise AND operation. The bitwise AND of all numbers in a range [L, R] is computed by right-shifting both L and R until they are equal, while counting the number of shifts. The common prefix is then left-shifted back to its original position. This approach effectively finds the common higher-order bits of the range.
Example: Consider an example where L=4 and R=8. We compute the AND of all numbers from 4 to 8 by observing patterns in the AND operation.
function rangeBitwiseAnd(L, R) {
let shift = 0;
while (L < R) {
L >>= 1;
R >>= 1;
shift++;
}
return L << shift;
}
let L = 4;
let R = 8;
console.log(rangeBitwiseAnd(L, R));
Output
0
Time Complexity: O(N) It iterates through each number in the range.
Space Complexity: O(1).
Compute the Bitwise AND of all Numbers in a Range using JavaScript
The complexity of bitwise AND computation for all numbers in a specific range is a common challenge faced by developers, particularly when optimizing algorithms. We have given two integers, L and R, and find the bitwise AND of all numbers in the inclusive range from L to R in JavaScript.
Example:
Let's consider an example where L=3 and R=6.
The bitwise AND of all numbers from 3 to 6 is calculated
as follows: 3&4&5&6 = (3&4) & (5&6)
= 0 & 4
= 0
Below are the approaches to compute the bitwise AND of all numbers in a range using JavaScript:
Table of Content
- Bitwise AND Property
- Bitwise Manipulation
Contact Us