Find position of k-th active bits in a number
Bit manipulation is a powerful technique used in computer programming to optimize various operations, especially when dealing with low-level tasks and memory constraints. In this article, we will discuss the problem of finding the position of the K-th active (set) bits in a given number using bitwise operations. We will walk through the problem statement, provide an explanation with a suitable example, present the pseudocode, discuss the algorithm in detail, and finally, explain the resultant output along with the time complexity of the solution.
Problem Statement:
The task at hand is to find the position (0-based index) of the K-th active bit in a given positive integer N. An active bit is a set bit, which means its value is 1 in the binary representation of the number. We need to write a function or method that takes the input integer N and the value of K and returns the position of the K-th active bit in N. If there are fewer than K active bits, the function should return an appropriate message indicating that the K-th active bit is not present.
Explanation with Example:
Let's understand the problem with an example. Consider the number N = 1000, which is represented in binary as 1111101000. If we look at the binary representation, there are five active bits (1s) at positions 3, 4, 5, 6, and 7 (0-based indexing). Now, suppose we want to find the position of the third active bit (K = 3) in N. The output should be 6 because the third active bit is present at the 6th position.
Pseudocode:
activeBitPosition(N, K):
if N < 0 or K <= 0:
return None
num = N
i = 0
counter = 0
while num > 0 and counter < K:
if num & 1 == 1:
counter++
if counter == K:
return i
num = num / 2
i++
return None
Algorithm Explanation:
The given pseudocode represents the function activeBitPosition(N, K), which takes the input integer N and the K value and returns the position of the K-th active bit in N. The algorithm follows these steps:
- Check if N is less than 0 or K is less than or equal to 0. If so, return None since the input is invalid.
- Initialize variables num to N, i to 0, and counter to 0. The variable num will be used to traverse through the binary representation of N, i will keep track of the current position, and counter will track the number of active bits found.
- Enter a while loop while num is greater than 0 and counter is less than K.
- Within the loop, check if the least significant bit of num (num & 1) is equal to 1. If so, increment the counter by 1 and check if counter is equal to K. If the condition is true, we have found the K-th active bit, so return the current position i.
- After the checks, right shift num by 1 (equivalent to num = num / 2) to move to the next bit position. Increment i to keep track of the current position.
- If the while loop completes and counter is still not equal to K, it means the K-th active bit is not present in N. In this case, return None to indicate that.
Code Solution
// C Program
// Find position of k-th active bits in a number
#include <stdio.h>
// Find kth active bit position
void activeBitPosition(int n, int k)
{
if (n < 0 || k <= 0)
{
return;
}
// Display given data
printf("\n Number : %d", n);
printf("\n %d-th Active Bit Position is : ", k);
int num = n;
int i = 0;
int counter = 0;
while (num > 0 && counter < k)
{
if (num & 1 == 1)
{
counter++;
if (counter == k)
{
// When we get kth active element
printf(" %d ", i);
}
}
// Same as of shift left side by 1 (num >> 1)
num /= 2;
// Next position
i++;
}
if (counter != k)
{
// When the kth active bit is not present
printf(" None \n");
}
}
int main()
{
// Test Case
// 25 = (11001) k = 1
activeBitPosition(25, 1);
// (1000) = (1111101000) k = 3
activeBitPosition(1000, 3);
// (153) = (10011001) k = 2
activeBitPosition(153, 2);
// (354) = (101100010) k = 4
// Position 8
activeBitPosition(354, 4);
// 25 = (11001) k = 5
activeBitPosition(25, 5);
return 0;
}Output
Number : 25
1-th Active Bit Position is : 0
Number : 1000
3-th Active Bit Position is : 6
Number : 153
2-th Active Bit Position is : 3
Number : 354
4-th Active Bit Position is : 8
Number : 25
5-th Active Bit Position is : None/*
Java Program for
Find position of k-th active bits in a number
*/
class BitPosition
{
// Find kth active bit position
public void activeBitPosition(int n, int k)
{
if (n < 0 || k <= 0)
{
return;
}
// Display given data
System.out.print("\n Number : " + n);
System.out.print("\n " + k + "-th Active Bit Position is :");
int num = n;
int i = 0;
int counter = 0;
while (num > 0 && counter < k)
{
if ((num & 1) == 1)
{
counter++;
if (counter == k)
{
// When we get kth active element
System.out.print(" " + i);
}
}
// Same as of shift left side by 1 (num >> 1)
num /= 2;
// Next position
i++;
}
if (counter != k)
{
// When the kth active bit is not present
System.out.print(" None \n");
}
}
public static void main(String[] args)
{
BitPosition task = new BitPosition();
// Test Case
// 25 = (11001) k = 1
task.activeBitPosition(25, 1);
// (1000) = (1111101000) k = 3
task.activeBitPosition(1000, 3);
// (153) = (10011001) k = 2
task.activeBitPosition(153, 2);
// (354) = (101100010) k = 4
// Position 8
task.activeBitPosition(354, 4);
// 25 = (11001) k = 5
task.activeBitPosition(25, 5);
}
}Output
Number : 25
1-th Active Bit Position is : 0
Number : 1000
3-th Active Bit Position is : 6
Number : 153
2-th Active Bit Position is : 3
Number : 354
4-th Active Bit Position is : 8
Number : 25
5-th Active Bit Position is : None// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Find position of k-th active bits in a number
*/
class BitPosition
{
public:
// Find kth active bit position
void activeBitPosition(int n, int k)
{
if (n < 0 || k <= 0)
{
return;
}
// Display given data
cout << "\n Number : " << n;
cout << "\n " << k << "-th Active Bit Position is :";
int num = n;
int i = 0;
int counter = 0;
while (num > 0 && counter < k)
{
// Next position
if ((num &1) == 1)
{
counter++;
if (counter == k)
{
// When we get kth active element
cout << " " << i;
}
}
// Same as of shift left side by 1 (num >> 1)
num /= 2;
i++;
}
if (counter != k)
{
// When the kth active bit is not present
cout << " None \n";
}
}
};
int main()
{
BitPosition task = BitPosition();
// Test Case
// 25 = (11001) k = 1
task.activeBitPosition(25, 1);
// (1000) = (1111101000) k = 3
task.activeBitPosition(1000, 3);
// (153) = (10011001) k = 2
task.activeBitPosition(153, 2);
// (354) = (101100010) k = 4
// Position 8
task.activeBitPosition(354, 4);
// 25 = (11001) k = 5
task.activeBitPosition(25, 5);
return 0;
}Output
Number : 25
1-th Active Bit Position is : 0
Number : 1000
3-th Active Bit Position is : 6
Number : 153
2-th Active Bit Position is : 3
Number : 354
4-th Active Bit Position is : 8
Number : 25
5-th Active Bit Position is : None// Include namespace system
using System;
/*
C# Program for
Find position of k-th active bits in a number
*/
public class BitPosition
{
// Find kth active bit position
public void activeBitPosition(int n, int k)
{
if (n < 0 || k <= 0)
{
return;
}
// Display given data
Console.Write("\n Number : " + n);
Console.Write("\n " + k + "-th Active Bit Position is :");
int num = n;
int i = 0;
int counter = 0;
while (num > 0 && counter < k)
{
// Next position
if ((num & 1) == 1)
{
counter++;
if (counter == k)
{
// When we get kth active element
Console.Write(" " + i);
}
}
// Same as of shift left side by 1 (num >> 1)
num /= 2;
i++;
}
if (counter != k)
{
// When the kth active bit is not present
Console.Write(" None \n");
}
}
public static void Main(String[] args)
{
BitPosition task = new BitPosition();
// Test Case
// 25 = (11001) k = 1
task.activeBitPosition(25, 1);
// (1000) = (1111101000) k = 3
task.activeBitPosition(1000, 3);
// (153) = (10011001) k = 2
task.activeBitPosition(153, 2);
// (354) = (101100010) k = 4
// Position 8
task.activeBitPosition(354, 4);
// 25 = (11001) k = 5
task.activeBitPosition(25, 5);
}
}Output
Number : 25
1-th Active Bit Position is : 0
Number : 1000
3-th Active Bit Position is : 6
Number : 153
2-th Active Bit Position is : 3
Number : 354
4-th Active Bit Position is : 8
Number : 25
5-th Active Bit Position is : None<?php
/*
Php Program for
Find position of k-th active bits in a number
*/
class BitPosition
{
// Find kth active bit position
public function activeBitPosition($n, $k)
{
if ($n < 0 || $k <= 0)
{
return;
}
// Display given data
echo "\n Number : ". $n;
echo "\n ". $k ."-th Active Bit Position is :";
$num = $n;
$i = 0;
$counter = 0;
while ($num > 0 && $counter < $k)
{
// Next position
if (($num & 1) == 1)
{
$counter++;
if ($counter == $k)
{
// When we get kth active element
echo " ". $i;
}
}
// Same as of shift left side by 1 (num >> 1)
$num = intval($num / 2);
$i++;
}
if ($counter != $k)
{
// When the kth active bit is not present
echo " None \n";
}
}
}
function main()
{
$task = new BitPosition();
// Test Case
// 25 = (11001) k = 1
$task->activeBitPosition(25, 1);
// (1000) = (1111101000) k = 3
$task->activeBitPosition(1000, 3);
// (153) = (10011001) k = 2
$task->activeBitPosition(153, 2);
// (354) = (101100010) k = 4
// Position 8
$task->activeBitPosition(354, 4);
// 25 = (11001) k = 5
$task->activeBitPosition(25, 5);
}
main();Output
Number : 25
1-th Active Bit Position is : 0
Number : 1000
3-th Active Bit Position is : 6
Number : 153
2-th Active Bit Position is : 3
Number : 354
4-th Active Bit Position is : 8
Number : 25
5-th Active Bit Position is : None/*
Node Js Program for
Find position of k-th active bits in a number
*/
class BitPosition
{
// Find kth active bit position
activeBitPosition(n, k)
{
if (n < 0 || k <= 0)
{
return;
}
// Display given data
process.stdout.write("\n Number : " + n);
process.stdout.write("\n " + k + "-th Active Bit Position is :");
var num = n;
var i = 0;
var counter = 0;
while (num > 0 && counter < k)
{
// Next position
if ((num & 1) == 1)
{
counter++;
if (counter == k)
{
// When we get kth active element
process.stdout.write(" " + i);
}
}
// Same as of shift left side by 1 (num >> 1)
num = parseInt(num / 2);
i++;
}
if (counter != k)
{
// When the kth active bit is not present
process.stdout.write(" None \n");
}
}
}
function main()
{
var task = new BitPosition();
// Test Case
// 25 = (11001) k = 1
task.activeBitPosition(25, 1);
// (1000) = (1111101000) k = 3
task.activeBitPosition(1000, 3);
// (153) = (10011001) k = 2
task.activeBitPosition(153, 2);
// (354) = (101100010) k = 4
// Position 8
task.activeBitPosition(354, 4);
// 25 = (11001) k = 5
task.activeBitPosition(25, 5);
}
main();Output
Number : 25
1-th Active Bit Position is : 0
Number : 1000
3-th Active Bit Position is : 6
Number : 153
2-th Active Bit Position is : 3
Number : 354
4-th Active Bit Position is : 8
Number : 25
5-th Active Bit Position is : None# Python 3 Program for
# Find position of k-th active bits in a number
class BitPosition :
# Find kth active bit position
def activeBitPosition(self, n, k) :
if (n < 0 or k <= 0) :
return
# Display given data
print("\n Number : ", n, end = "")
print("\n ", k ,"-th Active Bit Position is :", end = "")
num = n
i = 0
counter = 0
while (num > 0 and counter < k) :
if ((num & 1) == 1) :
counter += 1
if (counter == k) :
# When we get kth active element
print(" ", i, end = "")
num = int(num /
# Same as of shift left side by 1 (num >> 1)
2)
# Next position
i += 1
if (counter != k) :
# When the kth active bit is not present
print(" None ")
def main() :
task = BitPosition()
# Test Case
# 25 = (11001) k = 1
task.activeBitPosition(25, 1)
# (1000) = (1111101000) k = 3
task.activeBitPosition(1000, 3)
# (153) = (10011001) k = 2
task.activeBitPosition(153, 2)
# (354) = (101100010) k = 4
# Position 8
task.activeBitPosition(354, 4)
# 25 = (11001) k = 5
task.activeBitPosition(25, 5)
if __name__ == "__main__": main()Output
Number : 25
1 -th Active Bit Position is : 0
Number : 1000
3 -th Active Bit Position is : 6
Number : 153
2 -th Active Bit Position is : 3
Number : 354
4 -th Active Bit Position is : 8
Number : 25
5 -th Active Bit Position is : None# Ruby Program for
# Find position of k-th active bits in a number
class BitPosition
# Find kth active bit position
def activeBitPosition(n, k)
if (n < 0 || k <= 0)
return
end
# Display given data
print("\n Number : ", n)
print("\n ", k ,"-th Active Bit Position is :")
num = n
i = 0
counter = 0
while (num > 0 && counter < k)
if ((num & 1) == 1)
counter += 1
if (counter == k)
# When we get kth active element
print(" ", i)
end
end
# Same as of shift left side by 1 (num >> 1)
num /= 2
# Next position
i += 1
end
if (counter != k)
# When the kth active bit is not present
print(" None \n")
end
end
end
def main()
task = BitPosition.new()
# Test Case
# 25 = (11001) k = 1
task.activeBitPosition(25, 1)
# (1000) = (1111101000) k = 3
task.activeBitPosition(1000, 3)
# (153) = (10011001) k = 2
task.activeBitPosition(153, 2)
# (354) = (101100010) k = 4
# Position 8
task.activeBitPosition(354, 4)
# 25 = (11001) k = 5
task.activeBitPosition(25, 5)
end
main()Output
Number : 25
1-th Active Bit Position is : 0
Number : 1000
3-th Active Bit Position is : 6
Number : 153
2-th Active Bit Position is : 3
Number : 354
4-th Active Bit Position is : 8
Number : 25
5-th Active Bit Position is : None
/*
Scala Program for
Find position of k-th active bits in a number
*/
class BitPosition
{
// Find kth active bit position
def activeBitPosition(n: Int, k: Int): Unit = {
if (n < 0 || k <= 0)
{
return;
}
// Display given data
print("\n Number : " + n);
print("\n " + k + "-th Active Bit Position is :");
var num: Int = n;
var i: Int = 0;
var counter: Int = 0;
while (num > 0 && counter < k)
{
// Next position
if ((num & 1) == 1)
{
counter += 1;
if (counter == k)
{
// When we get kth active element
print(" " + i);
}
}
// Same as of shift left side by 1 (num >> 1)
num = (num / 2).toInt;
i += 1;
}
if (counter != k)
{
// When the kth active bit is not present
print(" None \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BitPosition = new BitPosition();
// Test Case
// 25 = (11001) k = 1
task.activeBitPosition(25, 1);
// (1000) = (1111101000) k = 3
task.activeBitPosition(1000, 3);
// (153) = (10011001) k = 2
task.activeBitPosition(153, 2);
// (354) = (101100010) k = 4
// Position 8
task.activeBitPosition(354, 4);
// 25 = (11001) k = 5
task.activeBitPosition(25, 5);
}
}Output
Number : 25
1-th Active Bit Position is : 0
Number : 1000
3-th Active Bit Position is : 6
Number : 153
2-th Active Bit Position is : 3
Number : 354
4-th Active Bit Position is : 8
Number : 25
5-th Active Bit Position is : None/*
Swift 4 Program for
Find position of k-th active bits in a number
*/
class BitPosition
{
// Find kth active bit position
func activeBitPosition(_ n: Int, _ k: Int)
{
if (n < 0 || k <= 0)
{
return;
}
// Display given data
print("\n Number : ", n, terminator: "");
print("\n ", k ,"-th Active Bit Position is :", terminator: "");
var num: Int = n;
var i: Int = 0;
var counter: Int = 0;
while (num > 0 && counter < k)
{
// Next position
if ((num & 1) == 1)
{
counter += 1;
if (counter == k)
{
// When we get kth active element
print(" ", i, terminator: "");
}
}
// Same as of shift left side by 1 (num >> 1)
num /= 2;
i += 1;
}
if (counter != k)
{
// When the kth active bit is not present
print(" None ");
}
}
}
func main()
{
let task: BitPosition = BitPosition();
// Test Case
// 25 = (11001) k = 1
task.activeBitPosition(25, 1);
// (1000) = (1111101000) k = 3
task.activeBitPosition(1000, 3);
// (153) = (10011001) k = 2
task.activeBitPosition(153, 2);
// (354) = (101100010) k = 4
// Position 8
task.activeBitPosition(354, 4);
// 25 = (11001) k = 5
task.activeBitPosition(25, 5);
}
main();Output
Number : 25
1 -th Active Bit Position is : 0
Number : 1000
3 -th Active Bit Position is : 6
Number : 153
2 -th Active Bit Position is : 3
Number : 354
4 -th Active Bit Position is : 8
Number : 25
5 -th Active Bit Position is : None/*
Kotlin Program for
Find position of k-th active bits in a number
*/
class BitPosition
{
// Find kth active bit position
fun activeBitPosition(n: Int, k: Int): Unit
{
if (n < 0 || k <= 0)
{
return;
}
// Display given data
print("\n Number : " + n);
print("\n " + k + "-th Active Bit Position is :");
var num: Int = n;
var i: Int = 0;
var counter: Int = 0;
while (num > 0 && counter < k)
{
// Next position
if ((num and 1) == 1)
{
counter += 1;
if (counter == k)
{
// When we get kth active element
print(" " + i);
}
}
// Same as of shift left side by 1 (num >> 1)
num /= 2;
i += 1;
}
if (counter != k)
{
// When the kth active bit is not present
print(" None \n");
}
}
}
fun main(args: Array < String > ): Unit
{
var task: BitPosition = BitPosition();
// Test Case
// 25 = (11001) k = 1
task.activeBitPosition(25, 1);
// (1000) = (1111101000) k = 3
task.activeBitPosition(1000, 3);
// (153) = (10011001) k = 2
task.activeBitPosition(153, 2);
// (354) = (101100010) k = 4
// Position 8
task.activeBitPosition(354, 4);
// 25 = (11001) k = 5
task.activeBitPosition(25, 5);
}Output
Number : 25
1-th Active Bit Position is : 0
Number : 1000
3-th Active Bit Position is : 6
Number : 153
2-th Active Bit Position is : 3
Number : 354
4-th Active Bit Position is : 8
Number : 25
5-th Active Bit Position is : NoneResultant Output Explanation:
Let's now analyze the output of the provided test cases using the activeBitPosition function:
- activeBitPosition(25, 1): The binary representation of 25 is 11001. The 1st active bit is found at position 0 (0-based index), so the output is 0.
- activeBitPosition(1000, 3): The binary representation of 1000 is 1111101000. The 3rd active bit is found at position 6, so the output is 6.
- activeBitPosition(153, 2): The binary representation of 153 is 10011001. The 2nd active bit is found at position 3, so the output is 3.
- activeBitPosition(354, 4): The binary representation of 354 is 101100010. The 4th active bit is found at position 8, so the output is 8.
- activeBitPosition(25, 5): The binary representation of 25 is 11001. There are only 3 active bits, so the 5th active bit is not present. The output is None.
Time Complexity of the Solution:
The time complexity of the given solution is O(log N), where N is the input integer. This is because the algorithm iterates through the bits of N at most log N times, as we perform a right shift by 1 (num = num / 2) in each iteration. The number of bits in N is proportional to log N in base 2, making it the time complexity of the algorithm.
Bit manipulation problems like this one can often lead to efficient solutions for various programming challenges. Understanding the bitwise operators and their applications can be beneficial in competitive programming, system-level programming, and various other fields where low-level manipulation is required. The provided solution efficiently solves the problem of finding the position of the K-th active bit in a given number.
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