How to extract ‘k’ bits from a given position ‘p’ in a number? Examples:
Input : number = 171
k = 5
p = 2
Output : The extracted number is 21
171 is represented as 10101011 in binary,
so, you should get only 10101 i.e. 21.
Input : number = 72
k = 5
p = 1
Output : The extracted number is 8
72 is represented as 1001000 in binary,
so, you should get only 01000 i.e 8.
We have existing solution for this problem please refer Extract ‘k’ bits from a given position in a number link. We can solve this problem quickly in python using slicing. Approach is simple,
- Convert given number into it’s binary using bin() function and remove first two characters ‘0b’ from it, because bin function appends ‘0b’ as prefix in output binary string.
- We need to start extracting k bits from starting position p from right, that means end index of extracted sub-string will be end = (len(binary) – p) and start index will be start = end – k + 1 of original binary string.
- Convert extracted sub-string into decimal again.
Python3
# Function to extract ‘k’ bits from a given# position in a numberdef extractKBits(num,k,p): # convert number into binary first binary = bin(num) # remove first two characters binary = binary[2:] end = len(binary) - p start = end - k + 1 # extract k bit sub-string kBitSubStr = binary[start : end+1] # convert extracted sub-string into decimal again print (int(kBitSubStr,2))# Driver programif __name__ == "__main__": num = 171 k = 5 p = 2 extractKBits(num,k,p) |
Output:
21
Time Complexity: O(logn)
Space Complexity: O(logn)
Method#2: Using Bitwise Operators
Approach
This approach defines a function named extract_bits that takes three arguments: number, k, and p. It returns the decimal value of the k bits starting from position p (from right to left) in the binary representation of number. The function first right-shifts the number by p-1 bits to get the desired bits at the rightmost end of the number. Then, it creates a mask by left-shifting 1 by k bits and subtracting 1 to get a binary number consisting of k ones. It then bitwise-ANDs the shifted number with the mask to extract the k bits. Finally, it converts the extracted bits to a binary string and then to an integer to get the decimal value.
Algorithm
1. Right shift the given number by p-1 bits to get the desired bits at the rightmost end of the number.
2. Mask the rightmost k bits to get rid of any additional bits on the left.
3. Convert the resulting bits to decimal using the int() function.
Python3
def extract_bits(number, k, p): # Right shift the number by p-1 bits to get the desired bits at the rightmost end of the number shifted_number = number >> (p-1) # Mask the rightmost k bits to get rid of any additional bits on the left mask = (1 << k) - 1 extracted_bits = shifted_number & mask # Convert the extracted bits to decimal extracted_number = bin(extracted_bits)[2:] decimal_value = int(extracted_number, 2) return decimal_valuenumber = 171k = 5p = 2print(extract_bits(number, k, p)) |
21
Time Complexity: O(1)
Space Complexity: O(1)
Approach#3: Using lambda
This approach takes a decimal number num, the number of bits k, and the position of the bits p as input. It converts num to a binary string using the bin() function, removes the ‘0b’ prefix from the string, and extracts a substring of length k starting from position p. Finally, the substring is converted back to an integer using the int() function with a base of 2.
Algorithm
1. Convert the decimal number to a binary string using bin().
2. Remove the ‘0b’ prefix from the binary string.
3. Extract a substring of length k starting from position p.
4. Convert the substring back to an integer using int() with a base of 2.
5. Return the extracted integer.
Python3
extract_bits = lambda num, k, p: int(bin(num)[2:][p:p+k], 2)print(extract_bits(171, 5, 2)) |
21
Time complexity: O(1), The time complexity of bin() and int() is O(log n), where n is the input number, but the input num is limited to 32 bits (in most implementations of Python), so the time complexity can be considered constant.
Auxiliary Space: O(log n) The space complexity of bin() and int() is O(log n), where n is the input number, but the input num is limited to 32 bits (in most implementations of Python), so the space complexity can be considered constant.
