JavaScript Program to Find First Set Bit
The rightmost bit in a binary representation of a number that is set to 1 is called the âFirst Set Bitâ. It indicates the lowest significant bit where the value changes from 0 to 1.
Examples:
Input:
N = 18
Output:
2
Explanation:
Binary representation of 18 is 010010,the first set bit from the right side is at position 2.
Input:
N = 12
Output:
3
Explanation:
Binary representation of 12 is 1100, the first set bit from the right side is at position 3.
Table of Content
- Using bitwise AND and shifting
- Using logarithm and bitwise right shift
- Using String Conversion
Using bitwise AND and shifting
In this approach, we are using the bitwise AND (&) operator with 1 to check each bit of the number from right to left. If a set bit is found, we determine its position by incrementing a counter variable (res) and breaking the loop.
Example: Implementation to use bitwise AND and shifting to find the first set bit.
let num = 18;
let res = 0;
while (num > 0) {
res++;
if (num & 1) {
console.log("Position of first set bit:", res);
break;
}
num >>= 1;
}
if (num === 0) {
console.log("No set bit found");
}
Output
Position of first set bit: 2
Time Complexity: O(log n)
Auxiliary Space: O(1)
Using logarithm and bitwise right shift
In this approach, we are using bitwise AND (&) with the twoâs complement of the number to isolate the rightmost set bit. Then, we use the logarithm (base 2) to find its position, accounting for 1-based indexing, to determine the position of the first set bit.
Example: Implementation to use logarithm and bitwise right shift to find the first set bit.
let num = 12;
if (num === 0) {
console.log("No set bit found");
} else {
console.log("Position of first set bit:",
Math.floor(Math.log2(num & -num)) + 1);
}
Output
Position of first set bit: 3
Time Complexity: O(1)
Auxiliary Space: O(1)
Using String Conversion
In this approach, we convert the given number to its binary representation using string conversion. Then, we find the index of the first â1â character in the binary string, representing the position of the first set bit. This method offers simplicity but might be less efficient compared to bitwise operations.
Example: Implementation to use logarithm and bitwise right shift to find the first set bit.
function findFirstSetBitString(number) {
const binaryString = number.toString(2);
const firstSetBitIndex =
binaryString.length - binaryString.indexOf('1');
return firstSetBitIndex;
}
console.log(findFirstSetBitString(10));
Output
4
Time Complexity: O(log n)
Auxiliary Space: O(log n)
Conclusion
In this article, we explored multiple approaches to finding the position of the first set bit in a number using JavaScript. Depending on the requirements and constraints of your application, you can choose the most suitable approach. While bitwise operations offer efficiency, logarithmic functions provide a concise solution, and string conversion offers simplicity at the cost of performance.
Contact Us