 # Python Program to Find Position of Rightmost 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).

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.