BITMEDU4 - Editorial

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.