Posted on by Kalkicode
Code Bit Logic

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.

Finding position of K-th set bit of number

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:

  1. 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.
  2. 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.
  3. Enter a while loop while num is greater than 0 and counter is less than K.
  4. 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.
  5. 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.
  6. 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 : None

Resultant Output Explanation:

Let's now analyze the output of the provided test cases using the activeBitPosition function:

  1. 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.
  2. activeBitPosition(1000, 3): The binary representation of 1000 is 1111101000. The 3rd active bit is found at position 6, so the output is 6.
  3. activeBitPosition(153, 2): The binary representation of 153 is 10011001. The 2nd active bit is found at position 3, so the output is 3.
  4. activeBitPosition(354, 4): The binary representation of 354 is 101100010. The 4th active bit is found at position 8, so the output is 8.
  5. 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.

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