Skip to main content

Find position of rightmost set bit

The problem of finding the position of the rightmost set bit in a given integer is a common task in computer programming. This position refers to the position of the least significant bit (LSB) that is set to 1 in the binary representation of the number.

Problem Statement

Given an integer n, the task is to find the position of the rightmost set bit in its binary representation.

Example

Let's consider an example with n = 320.

Binary representation of 320: 00101000000

The rightmost set bit is at position 7 (0-indexed), counting from the right. So, the output for this example should be Number: 320, Result: 7.

Idea to Solve

Position of rightmost set bit

The idea to solve this problem is to use the logarithm property. The position of the rightmost set bit in a binary number can be calculated using the formula log2(n & -n) + 1.

Pseudocode

function rightmostActiveBit(n):
    if n <= 0:
        return

    result = log2(n & -n) + 1
    print("Number:", n, "Result:", result)

Algorithm Explanation

  1. The rightmostActiveBit function takes an integer n as input.
  2. It checks if n is less than or equal to 0. If true, it returns as there is no rightmost set bit.
  3. The expression n & -n gives a number with only the rightmost set bit of n turned on.
  4. The logarithm base 2 of n & -n calculates the position of the rightmost set bit.
  5. Adding 1 to the result provides the position of the rightmost set bit.
  6. The function prints the original number and the calculated result.

Code Solution

Resultant Output Explanation

The output displays the input number and the calculated position of the rightmost set bit. For example, for rightmostActiveBit(320), the output is Number: 320, Result: 7, which means the rightmost set bit in the binary representation of 320 is at position 7.

Time Complexity

The time complexity of this algorithm is O(1), as it involves basic arithmetic and logarithmic calculations that do not depend on the input size.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment