Problem Link - Least significant bit, and 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 flip the least significant and most significant bits of a given integer n. First, the least significant bit (LSB), which is the rightmost bit, is flipped using a bitwise XOR operation with 1
(n = n ^ 1
). This toggles the LSB between 0 and 1. Next, to find the position of the most significant bit (MSB), we use a copy of n and continuously divide it by 2, counting each division until the number becomes zero. The count gives the MSB’s position. Finally, we flip this MSB by performing a bitwise XOR with (1 << pos)
, which shifts 1
to the MSB’s position and toggles it.
Time Complexity:
O(log(n)), due to dividing n by 2 repeatedly to find the most significant bit position.
Space Complexity:
O(1), as only a constant amount of extra space is used for variables.