Program to Find Position of Rightmost Set Bit

Find first set bit – Python Program to Find Position of Rightmost Set Bit

by

Find first set bit: In the previous article, we have discussed Python Program for Efficient Way to Multiply With 7

Give a number the task is to find the position of the rightmost set bit of the given number in Python.

Examples:

Example1:

Input:

Given Number = 22

Output:

The first set bit position of the given number { 22 } with binary string value { 10110 } = 2

Example2:

Input:

Given Number = 40

Output:

The first set bit position of the given number { 40 } with binary string value { 101000 } = 4

Program to Find Position of Rightmost Set Bit in Python

Below are the ways to find the position of the Rightmost set bit of the given number in Python:

Algorithm:

  • Let us take the given number 12.
  • The binary equivalent of the given number is 1100
  • Take the two’s complement of the provided number, excluding the first ‘1’ from right to left (0100).
  • Do a bit-wise & with the original no; this will return no with only the required one (0100).
  • If you take log2 of the number, you will obtain (position – 1).
  • Add 1.

Explanation:

  • (n&~(n-1)) Always return 1 for the binary number containing the rightmost set bit.
  • If N equals 12 (1100), it will return 4 (100).
  • In this case, log2 will return the number of times that number may be expressed in powers of two.
  • For all binary numbers with only the rightmost set bit as 1, such as 2, 4, 8, 16, 32…
  • We’ll discover that the position of the rightmost set bit is always equal to log2(Number)+1.

Method #1: Using log() Function (Static Input)

Approach:

  • Import the math function using the import keyword.
  • Create a function getFirstSetBitPosition() which accepts the given number as the argument and returns the position of the first set bit of the given number.
  • Inside the getFirstSetBitPosition() function.
  • Calculate and the value of log2(n&-n)+1 which gives the first set bit position of the given number and store it in a variable say result_pos.
  • Return the value of result_pos(Which is the position of the first set bit).
  • Inside the main code.
  • Give the number as static input and store it in a variable.
  • Pass the given number as the argument to getFirstSetBitPosition() function and store the result in a variable (firstSetBitposi).
  • Print the firstSetBitposi value.
  • The Exit of the Program.

Below is the implementation:

# Import the math function using the import keyword.
import math
# Create a function getFirstSetBitPosition()
# which accepts the given number as the argument and
# returns the position of the first set bit of the given number.


def getFirstSetBitPosition(numb):
    # Inside the getFirstSetBitPosition() function.
    # Calculate and the value of log2(n&-n)+1 which gives the first set bit position
    # of the given number and store it in a variable say result_pos.
    result_pos = math.log2(numb & -numb)+1
    # Return the value of result_pos(Which is the position of the first set bit).
    return int(result_pos)


# Inside the main code.
# Give the number as static input and store it in a variable.
gvnnumb = 22
# Pass the given number as the argument to getFirstSetBitPosition() 
# function and store the result in a variable(firstSetBitposi).
firstSetBitposi = getFirstSetBitPosition(gvnnumb)
# Print the firstSetBitposi value.
print('The first set bit position of the given number {', gvnnumb, '} with binary string value {', bin(
    gvnnumb)[2:], '} =', firstSetBitposi)

Output:

The first set bit position of the given number { 22 } with binary string value { 10110 } = 2

Method #2: Using log() Function (User Input)

Approach:

  • Import the math function using the import keyword.
  • Create a function getFirstSetBitPosition() which accepts the given number as the argument and returns the position of the first set bit of the given number.
  • Inside the getFirstSetBitPosition() function.
  • Calculate and the value of log2(n&-n)+1 which gives the first set bit position of the given number and store it in a variable say result_pos.
  • Return the value of result_pos(Which is the position of the first set bit).
  • Inside the main code.
  • Give the number as user input using the int(input())) function and store it in a variable.
  • Pass the given number as the argument to getFirstSetBitPosition() function and store the result in a variable (firstSetBitposi).
  • Print the firstSetBitposi value.
  • The Exit of the Program.

Below is the implementation:

# Import the math function using the import keyword.
import math
# Create a function getFirstSetBitPosition()
# which accepts the given number as the argument and
# returns the position of the first set bit of the given number.


def getFirstSetBitPosition(numb):
    # Inside the getFirstSetBitPosition() function.
    # Calculate and the value of log2(n&-n)+1 which gives the first set bit position
    # of the given number and store it in a variable say result_pos.
    result_pos = math.log2(numb & -numb)+1
    # Return the value of result_pos(Which is the position of the first set bit).
    return int(result_pos)


# Inside the main code.
# Give the number as user input using the int(input())) function and store it in a variable.
gvnnumb = int(input('Enter some random number = '))
# Pass the given number as the argument to getFirstSetBitPosition() 
# function and store the result in a variable(firstSetBitposi).
firstSetBitposi = getFirstSetBitPosition(gvnnumb)
# Print the firstSetBitposi value.
print('The first set bit position of the given number {', gvnnumb, '} with binary string value {', bin(
    gvnnumb)[2:], '} =', firstSetBitposi)

Output:

Enter some random number = 40
The first set bit position of the given number { 40 } with binary string value { 101000 } = 4

Remediate your knowledge gap by attempting the Python Code Examples regularly and understand the areas of need and work on them.