JavaScript Program to Compute the Bitwise OR of all Numbers in a Range
In JavaScript, bitwise operations provide a way to manipulate individual bits of numeric values. The bitwise OR operation (|) combines the bits of two operands, resulting in a new value where each bit is set if it is set in either operand.
Understanding Bitwise OR
The bitwise OR operation takes two operands and performs a logical OR operation on each pair of corresponding bits. If either bit in the operands is set (1), the corresponding bit in the result will also be set (1). Otherwise, the bit will be cleared (0). Here’s a quick overview of the bitwise OR truth table:
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
Table of Content
- Using Brute Force
- Optimised Approach
Using Brute Force
In this approach, we start by iterating through the numbers in the given range from left to right. For each number, we perform a bitwise OR operation with the result, updating it accordingly. Before computation, we check for a valid range, ensuring both left and right are greater than 0 and left is less than right. Finally, we return the computed result.
Example: Implementation to compute the bitwise OR of all numbers in a range using brute force approach.
function bitwiseOR(left, right) {
if (left < 0 || right < 0 || left > right) {
console.log("Invalid range");
return;
}
let result = 0;
for (let i = left; i <= right; i++) {
result = result | i;
}
return result;
}
const left = 3;
const right = 7;
console.log(bitwiseOR(left, right));
Output
7
Time Complexity: O(n)
Space Complexity: O(1)
Optimised Approach
In this approach, the function calculates the bitwise OR of numbers in the range from ‘start’ to ‘end’. It first computes the bitwise OR of numbers from 1 to ‘start – 1’ and from 1 to ‘end’, then combines them to find the result.
Example: Implementation to compute the bitwise OR of all numbers in a range with an optimised solution.
function ORN(n) {
if (n % 2 === 0) return n - 1;
return n;
}
function ORRange(start, endValue) {
const startMinusOne = ORN(start - 1);
const end = ORN(endValue);
return startMinusOne | end;
}
const startValue = 3;
const endValue = 7;
const result = ORRange(startValue, endValue);
console.log(result);
Output
7
Time Complexity: O(1)
Space Complexity: O(1)