grid47 Exploring patterns and algorithms
Oct 19, 2024
4 min read
Solution to LeetCode 190: Reverse Bits Problem
Given a 32-bit unsigned integer, reverse its bits and return the result as an unsigned integer.
Problem
Approach
Steps
Complexity
Input: The input consists of a 32-bit unsigned integer.
Example: n = 00000000000000000000000010011010
Constraints:
• The input is a 32-bit unsigned integer.
Output: The output is the 32-bit unsigned integer obtained by reversing the bits of the input integer.
Example: n = 11259375
Constraints:
• The result should be returned as an unsigned integer.
Goal: The goal is to reverse the bits of the given 32-bit unsigned integer and return the result.
Steps:
• Step 1: Perform bitwise manipulations to reverse the bits of the integer.
• Step 2: Apply bit shifting and masking to reverse pairs, nibbles, bytes, etc.
• Step 3: Return the result after all bitwise reversals.
Goal: The problem constraints ensure that the input is a valid 32-bit unsigned integer.
Steps:
• The input must be a 32-bit unsigned integer.
Assumptions:
• The input is a valid 32-bit unsigned integer.
• Input: Input: n = 00000000000000000000000010011010
• Explanation: The binary string represents the integer 250. Reversing the bits results in the output integer 11259375, whose binary representation is 0000000000000000101011001010000.
Approach: To solve this problem, we use bitwise operations to reverse the bits of the integer efficiently.
Observations:
• We can use a series of bitwise operations like shifting and masking to reverse the bits.
• Reversing bits requires operations that progressively swap and shift bits to their correct positions.
Steps:
• Step 1: Mask and shift the bits in pairs, nibbles, bytes, etc., progressively moving the bits to their correct reversed positions.
• Step 2: Combine the shifted bits using bitwise OR operations.
• Step 3: Return the final reversed integer.
Empty Inputs:
• The input is always a 32-bit unsigned integer, so no empty inputs are possible.
Large Inputs:
• The input is a fixed 32-bit integer, so no large inputs are required.
Special Values:
• Ensure the input is a valid unsigned 32-bit integer (i.e., values between 0 and 4294967295).
Constraints:
• Input is always a 32-bit unsigned integer.
uint32_treverseBits(uint32_t n) {
n = (n &0xffffffff) <<16| (n &0xffffffff) >>16;
n = (n &0x00ff00ff) <<8| (n &0xff00ff00) >>8;
n = (n &0x0f0f0f0f) <<4| (n &0xf0f0f0f0) >>4;
n = (n &0x33333333) <<2| (n &0xcccccccc) >>2;
n = (n &0x55555555) <<1| (n &0xaaaaaaaa) >>1;
return n;
}
1 : Function Definition
uint32_treverseBits(uint32_t n) {
Define the function 'reverseBits' which takes a 32-bit unsigned integer 'n' and returns its bit-reversed value.
2 : Bitwise Operation
n = (n &0xffffffff) <<16| (n &0xffffffff) >>16;
Perform a bitwise AND operation with '0xffffffff' to isolate all bits, then shift the left and right halves of 'n' to reverse their positions.
3 : Bitwise Operation
n = (n &0x00ff00ff) <<8| (n &0xff00ff00) >>8;
Shift the nibbles (4-bit sections) of 'n' by 8 positions, swapping each pair of adjacent nibbles.
4 : Bitwise Operation
n = (n &0x0f0f0f0f) <<4| (n &0xf0f0f0f0) >>4;
Shift the 4-bit blocks of 'n' by 4 positions, swapping adjacent blocks.
5 : Bitwise Operation
n = (n &0x33333333) <<2| (n &0xcccccccc) >>2;
Shift the 2-bit pairs of 'n' by 2 positions, swapping each pair of bits.
6 : Bitwise Operation
n = (n &0x55555555) <<1| (n &0xaaaaaaaa) >>1;
Shift individual bits of 'n' by 1 position, swapping bits in each pair.
7 : Return Statement
return n;
Return the bit-reversed value of 'n'.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: The time complexity is O(1), as the number of operations is constant due to the fixed size of the input (32 bits).
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1), as we only need a fixed amount of space to store the result.
