Situatie
Given an unsigned integer, reverse all bits of it and return the number with reversed bits.
Input : n = 1
Output : 2147483648
Explanation : On a machine with size of unsigned bit as 32. Reverse of 0….001 is 100….0.
Solutie
Pasi de urmat
Loop through all the bits of an integer. If a bit at ith position is set in the i/p no. then set the bit at (NO_OF_BITS – 1) – i in o/p. Where NO_OF_BITS is number of bits present in the given number.
// C code to implement the approach
#include <stdio.h>
// Function to reverse bits of num
unsigned int reverseBits(unsigned int num)
{
unsigned int NO_OF_BITS = sizeof(num) * 8;
unsigned int reverse_num = 0;
int i;
for (i = 0; i < NO_OF_BITS; i++) {
if ((num & (1 << i)))
reverse_num |= 1 << ((NO_OF_BITS – 1) – i);
}
return reverse_num;
}
// Driver code
int main()
{
unsigned int x = 2;
printf(“%u”, reverseBits(x));
getchar();
}
Time Complexity: O(Log n). Time complexity would be Log(num) as there are log(num) bits in a binary number “num” and we’re looping through all bits.
Auxiliary space: O(1)
Leave A Comment?