Skip to main content

Reverse the bits of a number

The problem at hand involves reversing the bits of a given positive integer. In the context of computer systems, a binary representation is used to store and process data. Each binary digit, commonly known as a bit, can be either 0 or 1. Reversing the bits of a number means changing the order of these binary digits, effectively creating a new number that represents the original number with its bits flipped.

For example, if we have the number 35, which in binary is 100011, reversing its bits would result in 110001, which is the binary representation of 49.

Problem Statement

Reverse the bits of a given integer

The task is to write a program that takes a positive integer as input and outputs the new integer formed by reversing the bits of the input number. The program should include a method reverseBits that performs the bit reversal operation and a main method to test the function with different input numbers.

Idea to Solve the Problem

To reverse the bits of a number, we can start by initializing a variable result to 0. Then, for each bit in the input number, we'll check if it is set (i.e., equal to 1). If the bit is set, we'll set the corresponding bit in the result by performing a bitwise XOR operation with 1. After processing each bit, we'll left-shift the result by 1 to accommodate the next bit. This process continues until all the bits in the input number are processed.

Pseudocode

reverseBits(num):
    result = 0
    n = num
    while n is not 0:
        if result is not 0:
            result = result << 1
        if n & 1 is 1:
            result = result ^ 1
        n = n / 2
    return result

Algorithm Explanation

  1. Initialize result to 0 to store the reversed bits.
  2. Initialize n with the value of the input number num.
  3. Start a loop that continues until n becomes 0. a. If result is not 0 (meaning we have processed at least one bit), left-shift result by 1. b. Check the least significant bit of n using the bitwise AND operation (n & 1). If it's 1, perform a bitwise XOR operation with 1 on result to set the corresponding bit. c. Divide n by 2 to move on to the next bit in the next iteration.
  4. After the loop completes, the result will contain the reversed bits.
  5. Return the value of result.

Code Solution

Time Complexity

The time complexity of the reverseBits method is O(log n), where n is the input number. This is because the loop iterates for the number of bits in the input number, and the number of bits in a positive integer n is approximately log2(n).





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment