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
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
countSetBit(num)
calculates the number of active bits (set bits) in the given number using bit manipulation techniques. The complexlooking bitwise operations help count the bits in a more efficient way.shiftActiveBits(num)
uses thecountSetBit
function to count the active bits in the given number. 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.
 The result is printed along with the given number.
Code Solution

1) Transpose all set bits to the end of given number in java
2) Transpose all set bits to the end of given number in c++
3) Transpose all set bits to the end of given number in c
4) Transpose all set bits to the end of given number in c#
5) Transpose all set bits to the end of given number in vb.net
6) Transpose all set bits to the end of given number in php
7) Transpose all set bits to the end of given number in node js
8) Transpose all set bits to the end of given number in typescript
9) Transpose all set bits to the end of given number in python
10) Transpose all set bits to the end of given number in ruby
11) Transpose all set bits to the end of given number in scala
12) Transpose all set bits to the end of given number in swift
13) Transpose all set bits to the end of given number in kotlin
14) Transpose all set bits to the end of given number in golang
Resultant Output Explanation
For the given code and the provided test cases, let's break down the output:

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".

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.
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