Posted on by Kalkicode
Code Bit Logic

# Find position of all active bits in a number

The problem of finding the positions of all active bits (set bits) in a given number is a common task in computer science and digital systems. Set bits are the binary digits that are turned on (1) in a binary representation of a number. This problem has applications in various areas such as binary operations, encoding schemes, and algorithms dealing with bit manipulation.

## Problem Statement and Description

Given a positive integer `n`, we are required to find and display the positions of all the active bits (set bits) in its binary representation. For instance, if we take the number 23, its binary representation is 10111. The set bits are at positions 0, 1, 2, and 4 (reading from right to left). Similarly, for the number 16 (binary: 10000), the only set bit is at position 4.

## Examples

• For `23`: The binary representation of 23 is 10111. The active bit positions are 0, 1, 2, and 4.
• For `16`: The binary representation of 16 is 10000. The active bit position is 4.
• For `21`: The binary representation of 21 is 10101. The active bit positions are 0, 2, and 4.
• For `0`: There are no set bits in the binary representation, so "None" is printed.

## Idea to Solve the Problem

The idea to solve this problem involves iterating through the binary digits of the given number and identifying the positions where the digit is 1. We can achieve this by repeatedly dividing the number by 2 (using bitwise shift operation) and checking the remainder. If the remainder is 1, then the current bit is a set bit and its position is recorded.

## Pseudocode and Algorithm

``````Function activeBitPosition(n):
if n < 0:
return
i = 0
num = n
status = false
print "Number:", n
print "Active Bit Position:",
while num > 0:
if num % 2 == 1:
status = true
print i,
num = num / 2
i = i + 1
if status == false:
print "None"``````

## Explanation of Algorithm

1. The `activeBitPosition` function takes an integer `n` as input.
2. If `n` is negative, the function returns without doing anything.
3. Initialize `i` to 0, which will be used to keep track of the current bit position.
4. Initialize `num` with the value of `n` and `status` as `false`.
5. Display the given number and the message "Active Bit Position:".
6. Enter a loop that continues as long as `num` is greater than 0.
7. Inside the loop, check if the remainder of `num` divided by 2 is 1. If it is, then the current bit is a set bit.
8. Set `status` to true and print the current value of `i`, which represents the position of the active bit.
9. Divide `num` by 2 (right-shift operation) to move to the next bit.
10. Increment `i` to move to the next position.
11. If no set bits were found (`status` is false), print "None".

## Time Complexity

The time complexity of this algorithm is O(log n), where `n` is the input number. This is because the algorithm iterates through the bits of the number by repeatedly dividing it by 2, and the number of iterations required is proportional to the number of bits in the binary representation of `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.

Categories
Relative Post