Skip to main content

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.

Find the position of set bits in a number

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

Code Solution

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.

New Comment