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
- Python Program to Print Binary Representation of a Number
- Python Program to Count Set Bits in a Number
- Python Program to Find Whether a Number is a Power of Two
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.