Problem Link - Finding least significant, most significant bit
Problem Statement
-
Write a program to input an integer N.
-
Print the position of the most significant bit, and print the least significant bit.
Approach
The code idea is to determine two key properties of the input integer N: the position of the most significant bit (MSB) and the value of the least significant bit (LSB).
-
Least Significant Bit (LSB): This is obtained by performing a bitwise AND operation between N and
1
. If N is odd, the LSB will be1
, and if it is even, the LSB will be0
. -
Most Significant Bit (MSB): The position of the MSB is found by repeatedly dividing N by
2
until N becomes0
, while keeping track of the number of divisions. The position of the MSB is then the count of divisions minus one since the counting starts from1
.
Time Complexity
The time complexity of the algorithm is O(log N), as it involves repeatedly dividing N by 2
.
Space Complexity
The space complexity of the algorithm is O(1), since it uses a constant amount of space for variables.