Posted on by Kalkicode
Code Bit Logic

Shift active bits to the right side

The problem we're tackling involves shifting all the active (set) bits to the right side of a given integer while maintaining their relative order. Active bits are the bits with a value of 1 in the binary representation of the number. The task is to devise a method to shift these active bits to the right side of the number.

Problem Statement and Description

Given an integer num, we want to rearrange its bits in such a way that all the active bits (1s) are moved to the right side of the number while keeping their relative order unchanged. For example, if we have the number 21 (binary: 10101), we want to move its active bits to the right to get 7 (binary: 111), which is the result. The task is to develop an efficient algorithm to achieve this bit rearrangement.

Example

Consider the number 21. In binary, 21 is represented as 10101. The active bits are at positions 0, 2, and 4. By shifting these active bits to the right, we get 111 in binary, which is equal to 7. Therefore, for this example, the expected output should be "After Shift: 7".

Another example is the number 12. In binary, 12 is represented as 1100. The active bits are at positions 2 and 3. By shifting these active bits to the right, we get 11 in binary, which is equal to 3. Thus, the expected output for this example should be "After Shift: 3".

Idea to Solve the Problem

Move the set bit of the given number to the right

The core idea to solve this problem is to calculate the number of active bits in the given integer and then use bit manipulation to perform the shift operation.

Pseudocode

Here's the pseudocode for the algorithm:

function countSetBit(num):
    x = num
    x = x - ((x >> 1) & 1431655765)
    x = (x & 858993459) + ((x >> 2) & 858993459)
    x = (x + (x >> 4)) & 252645135
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x & 63
    return x

function shiftActiveBits(num):
    print "Given num:", num
    result = (1 << countSetBit(num)) - 1
    print "After Shift:", result

Algorithm Explanation

  1. countSetBit(num) calculates the number of active bits (set bits) in the given number using bit manipulation techniques. The complex-looking bitwise operations help count the bits in a more efficient way.
  2. shiftActiveBits(num) uses the countSetBit function to count the active bits in the given number.
  3. It then shifts the value 1 left by the number of active bits and subtracts 1 to generate a binary number with all the active bits on the right side.
  4. The result is printed along with the given number.

Code Solution

Resultant Output Explanation

For the given code and the provided test cases, let's break down the output:

  1. For the number 21:

    • Binary representation: 10101
    • Number of active bits: 3
    • Shifting 1 by 3 positions gives 1000.
    • Subtracting 1 gives 111.
    • The output is "Given num: 21\nAfter Shift: 7".
  2. For the number 12:

    • Binary representation: 1100
    • Number of active bits: 2
    • Shifting 1 by 2 positions gives 100.
    • Subtracting 1 gives 11.
    • The output is "Given num: 12\nAfter Shift: 3".

Time Complexity

The time complexity of the algorithm primarily depends on the calculation of the number of active bits, which involves bitwise operations. These bitwise operations are efficient and generally execute in constant time. Thus, the time complexity of the algorithm is O(1), or constant time.

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