JavaScript Program to Find the Position of the Rightmost Set Bit
Given a number, the task is to find the position of the rightmost set bit. The indexing is from right to left, where the rightmost bit position starts from 1.
Example:
Input: n = 20
Output: 3
Explanation: Binary Representation of 20 is 10100, hence position of first set bit from right is 3.
Input: n = 48
Output: 5
Explanation: Binary Representation of 48 is 110000, hence position of first set bit from right is 5.
Below are the approaches to finding the position of the rightmost set bit using JavaScript:
Table of Content
- Using (n & ~ (n – 1))
- Using & and shift operator
Using (n & ~ (n – 1))
Take 2’s complement of the given number as all bits are reverted except the first ‘1’ from right. 2’s complement is negation (~) of the given number + 1 (i.e. ~ n + 1). Do a bit-wise & with original no, this will return number with the required rightmost set bit. Take the log2 of the number got in step 2, you will get (position – 1), add 1 to it to get the position.
Example: The example below shows how to return the position of the rightmost set bit in JavaScript using (n & ~ (n -1)).
function rightBitPos(n) {
if (n === 0) {
return -1;
// Return -1 for the case where n is 0
}
return Math.log2(n & (~(n - 1))) + 1;
}
// Driver code
let n = 20;
console.log(rightBitPos(n));
Output
3
Time Complexity: O(log2n), time taken by log2 function.
Auxiliary Space: O(1)
Using & and shift operator
Initialize m as 1 and check its & with the bits, starting from the rightmost bit. Left shift m by one till we find the first set bit. The first set bit will give a number when we perform & operation with m.
Example: The example below shows how to return the position of the rightmost set bit in JavaScript using & and shift operator.
function rightBit(n) {
let position = 1;
let m = 1;
while ((n & m) == 0) {
// left shift
m = m << 1;
position++;
}
return position;
}
let n = 20;
// function call
console.log(rightBit(n));
Output
3
Time Complexity: O(log2n)
Auxiliary Space: O(1)
Contact Us