Posted on by Kalkicode
Code Bit Logic

Count all unset bit in given range

The given problem is to count all the unset bits (inactive bits with value 0) in a given range [low, high] of a given positive integer num. The range is specified by two integers low and high, where low and high are the positions (1-indexed) of the bits from the right side of the binary representation of num. The goal is to count the number of inactive bits within the specified range.

Problem Statement with Example

Let's understand the problem with an example. Consider the following binary representations of two numbers:

  1. num = 104, represented as (1101000) in binary.
  2. num = 786, represented as (1100010010) in binary.

We will perform two queries in this example:

  1. low = 2 and high = 5 for num = 104.
  2. low = 3 and high = 8 for num = 786.

Query 1 (num = 104, low = 2, high = 5)

  • Binary representation of num = 104 is (1101000).
  • We are interested in the bits from position 2 to position 5 (inclusive) from the right side, which is 0100.
  • There are three inactive bits (0) within this range.

Query 2 (num = 786, low = 3, high = 8)

  • Binary representation of num = 786 is (1100010010).
  • We are interested in the bits from position 3 to position 8 (inclusive) from the right side, which is 000100.
  • There are five inactive bits (0) within this range.

Pseudocode

countUnsetBit(num, low, high):
    if num < 0 or low < 1 or high < 1 or high > 31:
        return
    count = 0
    for i = low to high:
        if (1 << (i - 1)) & num == 0:
            count++
    output count

Algorithm

The algorithm for counting unset bits in the given range can be summarized as follows:

  1. Input the positive integer num, and the range boundaries low and high.
  2. Check if the input is valid, i.e., if num is positive and low and high are within the valid range (1 to 31).
  3. Initialize a variable count to 0, which will keep track of the number of unset bits within the specified range.
  4. Iterate from low to high (inclusive):
    • Check if the bit at the current position is unset (0) in the binary representation of num.
    • If it is unset, increment the count by 1.
  5. Output the value of count, which represents the number of unset bits within the given range.

Code Solution

Here given code implementation process.

// C Program
// Count all unset bit in given range 
#include <stdio.h>

// This is counting the all inactive bits in a given range
void countUnsetBit(int num, int low, int high)
{
	if (num < 0 || low < 1 || high < 1 || high > 31)
	{
		return;
	}
	int i = low;
	// bit counter
	int count = 0;
	// Display given numbers
	printf("\n Given Num : %d", num);
	printf("\n Range     : (%d,%d)", low, high);
	// Check bits in given range
	while (i <= high && (1 << (i - 1)) <= num)
	{
		if (((1 << (i - 1)) & num) == 0)
		{
			// When the bit is inactive
			count++;
		}
		i++;
	}
	// Display calculated result
	printf("\n Unset Bit : %d\n", count);
}
int main(int argc, char
	const *argv[])
{
	// Test case
	// num = 104 , low = 2, high = 5
	// 104 => (1101000)
	//           ----
	countUnsetBit(104, 2, 5);
	// num = 786 , low = 3, high = 8 
	// 786 => (1100010010)
	//           ------
	countUnsetBit(786, 3, 8);
	return 0;
}

Output

 Given Num : 104
 Range     : (2,5)
 Unset Bit : 3

 Given Num : 786
 Range     : (3,8)
 Unset Bit : 5
/*
  Java program
  Append a set bit in given position of a number
*/
public class Counting
{
	// This is counting the all inactive bits in a given range
	public void countUnsetBit(int num, int low, int high)
	{
		if (num < 0 || low < 1 || high < 1 || high > 31)
		{
			return;
		}
		int i = low;
		// bit counter
		int count = 0;
		// Display given numbers
		System.out.print("\n Given Num : " + num);
		System.out.print("\n Range : (" + low + "," + high + ")");
		// Check bits in given range
		while (i <= high && (1 << (i - 1)) <= num)
		{
			if (((1 << (i - 1)) & num) == 0)
			{
				// When the bit is inactive
				count++;
			}
			i++;
		}
		// Display calculated result
		System.out.print("\n Unset Bit : " + count + "\n");
	}
	public static void main(String[] args)
	{
		Counting task = new Counting();
		// Test case
		// num = 104 , low = 2, high = 5
		// 104 => (1101000)
		//           ----
		task.countUnsetBit(104, 2, 5);
		// num = 786 , low = 3, high = 8 
		// 786 => (1100010010)
		//           ------
		task.countUnsetBit(786, 3, 8);
	}
}

Output

 Given Num : 104
 Range : (2,5)
 Unset Bit : 3

 Given Num : 786
 Range : (3,8)
 Unset Bit : 5
// Include header file
#include <iostream>
using namespace std;

/*
  C++ program
  Append a set bit in given position of a number
*/

class Counting
{
	public:
		// This is counting the all inactive bits in a given range
		void countUnsetBit(int num, int low, int high)
		{
			if (num < 0 || low < 1 || high < 1 || high > 31)
			{
				return;
			}
			int i = low;
			// bit counter
			int count = 0;
			// Display given numbers
			cout << "\n Given Num : " << num;
			cout << "\n Range : (" << low << "," << high << ")";
			// Check bits in given range
			while (i <= high && (1 << (i - 1)) <= num)
			{
				if (((1 << (i - 1)) &num) == 0)
				{
					// When the bit is inactive
					count++;
				}
				i++;
			}
			// Display calculated result
			cout << "\n Unset Bit : " << count << "\n";
		}
};
int main()
{
	Counting task = Counting();
	// Test case
	// num = 104 , low = 2, high = 5
	// 104 => (1101000)
	//           ----
	task.countUnsetBit(104, 2, 5);
	// num = 786 , low = 3, high = 8
	// 786 => (1100010010)
	//           ------
	task.countUnsetBit(786, 3, 8);
	return 0;
}

Output

 Given Num : 104
 Range : (2,5)
 Unset Bit : 3

 Given Num : 786
 Range : (3,8)
 Unset Bit : 5
// Include namespace system
using System;
/*
  C# program
  Append a set bit in given position of a number
*/
public class Counting
{
	// This is counting the all inactive bits in a given range
	public void countUnsetBit(int num, int low, int high)
	{
		if (num < 0 || low < 1 || high < 1 || high > 31)
		{
			return;
		}
		int i = low;
		// bit counter
		int count = 0;
		// Display given numbers
		Console.Write("\n Given Num : " + num);
		Console.Write("\n Range : (" + low + "," + high + ")");
		// Check bits in given range
		while (i <= high && (1 << (i - 1)) <= num)
		{
			if (((1 << (i - 1)) & num) == 0)
			{
				// When the bit is inactive
				count++;
			}
			i++;
		}
		// Display calculated result
		Console.Write("\n Unset Bit : " + count + "\n");
	}
	public static void Main(String[] args)
	{
		Counting task = new Counting();
		// Test case
		// num = 104 , low = 2, high = 5
		// 104 => (1101000)
		//           ----
		task.countUnsetBit(104, 2, 5);
		// num = 786 , low = 3, high = 8
		// 786 => (1100010010)
		//           ------
		task.countUnsetBit(786, 3, 8);
	}
}

Output

 Given Num : 104
 Range : (2,5)
 Unset Bit : 3

 Given Num : 786
 Range : (3,8)
 Unset Bit : 5
<?php
/*
  Php program
  Append a set bit in given position of a number
*/
class Counting
{
	// This is counting the all inactive bits in a given range
	public	function countUnsetBit($num, $low, $high)
	{
		if ($num < 0 || $low < 1 || $high < 1 || $high > 31)
		{
			return;
		}
		$i = $low;
		// bit counter
		$count = 0;
		// Display given numbers
		echo "\n Given Num : ". $num;
		echo "\n Range : (". $low .",". $high .")";
		// Check bits in given range
		while ($i <= $high && (1 << ($i - 1)) <= $num)
		{
			if (((1 << ($i - 1)) & $num) == 0)
			{
				// When the bit is inactive
				$count++;
			}
			$i++;
		}
		// Display calculated result
		echo "\n Unset Bit : ". $count ."\n";
	}
}

function main()
{
	$task = new Counting();
	// Test case
	// num = 104 , low = 2, high = 5
	// 104 => (1101000)
	//           ----
	$task->countUnsetBit(104, 2, 5);
	// num = 786 , low = 3, high = 8
	// 786 => (1100010010)
	//           ------
	$task->countUnsetBit(786, 3, 8);
}
main();

Output

 Given Num : 104
 Range : (2,5)
 Unset Bit : 3

 Given Num : 786
 Range : (3,8)
 Unset Bit : 5
/*
  Node Js program
  Append a set bit in given position of a number
*/
class Counting
{
	// This is counting the all inactive bits in a given range
	countUnsetBit(num, low, high)
	{
		if (num < 0 || low < 1 || high < 1 || high > 31)
		{
			return;
		}
		var i = low;
		// bit counter
		var count = 0;
		// Display given numbers
		process.stdout.write("\n Given Num : " + num);
		process.stdout.write("\n Range : (" + low + "," + high + ")");
		// Check bits in given range
		while (i <= high && (1 << (i - 1)) <= num)
		{
			if (((1 << (i - 1)) & num) == 0)
			{
				// When the bit is inactive
				count++;
			}
			i++;
		}
		// Display calculated result
		process.stdout.write("\n Unset Bit : " + count + "\n");
	}
}

function main()
{
	var task = new Counting();
	// Test case
	// num = 104 , low = 2, high = 5
	// 104 => (1101000)
	//           ----
	task.countUnsetBit(104, 2, 5);
	// num = 786 , low = 3, high = 8
	// 786 => (1100010010)
	//           ------
	task.countUnsetBit(786, 3, 8);
}
main();

Output

 Given Num : 104
 Range : (2,5)
 Unset Bit : 3

 Given Num : 786
 Range : (3,8)
 Unset Bit : 5
#   Python 3 program
#   Append a set bit in given position of a number

class Counting :
	#  This is counting the all inactive bits in a given range
	def countUnsetBit(self, num, low, high) :
		if (num < 0 or low < 1 or high < 1 or high > 31) :
			return
		
		i = low
		#  bit counter
		count = 0
		#  Display given numbers
		print("\n Given Num : ", num, end = "")
		print("\n Range : (", low ,",", high ,")", end = "")
		#  Check bits in given range
		while (i <= high and(1 << (i - 1)) <= num) :
			if (((1 << (i - 1)) & num) == 0) :
				#  When the bit is inactive
				count += 1
			
			i += 1
		
		#  Display calculated result
		print("\n Unset Bit : ", count )
	

def main() :
	task = Counting()
	#  Test case
	#  num = 104 , low = 2, high = 5
	#  104 => (1101000)
	#            ----
	task.countUnsetBit(104, 2, 5)
	#  num = 786 , low = 3, high = 8 
	#  786 => (1100010010)
	#            ------
	task.countUnsetBit(786, 3, 8)

if __name__ == "__main__": main()

Output

 Given Num :  104
 Range : ( 2 , 5 )
 Unset Bit :  3

 Given Num :  786
 Range : ( 3 , 8 )
 Unset Bit :  5
#   Ruby program
#   Append a set bit in given position of a number

class Counting 
	#  This is counting the all inactive bits in a given range
	def countUnsetBit(num, low, high) 
		if (num < 0 || low < 1 || high < 1 || high > 31) 
			return
		end

		i = low
		#  bit counter
		count = 0
		#  Display given numbers
		print("\n Given Num : ", num)
		print("\n Range : (", low ,",", high ,")")
		#  Check bits in given range
		while (i <= high && (1 << (i - 1)) <= num) 
			if (((1 << (i - 1)) & num) == 0) 
				#  When the bit is inactive
				count += 1
			end

			i += 1
		end

		#  Display calculated result
		print("\n Unset Bit : ", count ,"\n")
	end

end

def main() 
	task = Counting.new()
	#  Test case
	#  num = 104 , low = 2, high = 5
	#  104 => (1101000)
	#            ----
	task.countUnsetBit(104, 2, 5)
	#  num = 786 , low = 3, high = 8 
	#  786 => (1100010010)
	#            ------
	task.countUnsetBit(786, 3, 8)
end

main()

Output

 Given Num : 104
 Range : (2,5)
 Unset Bit : 3

 Given Num : 786
 Range : (3,8)
 Unset Bit : 5

/*
  Scala program
  Append a set bit in given position of a number
*/
class Counting
{
	// This is counting the all inactive bits in a given range
	def countUnsetBit(num: Int, low: Int, high: Int): Unit = {
		if (num < 0 || low < 1 || high < 1 || high > 31)
		{
			return;
		}
		var i: Int = low;
		// bit counter
		var count: Int = 0;
		// Display given numbers
		print("\n Given Num : " + num);
		print("\n Range : (" + low + "," + high + ")");
		// Check bits in given range
		while (i <= high && (1 << (i - 1)) <= num)
		{
			if (((1 << (i - 1)) & num) == 0)
			{
				// When the bit is inactive
				count += 1;
			}
			i += 1;
		}
		// Display calculated result
		print("\n Unset Bit : " + count + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Counting = new Counting();
		// Test case
		// num = 104 , low = 2, high = 5
		// 104 => (1101000)
		//           ----
		task.countUnsetBit(104, 2, 5);
		// num = 786 , low = 3, high = 8
		// 786 => (1100010010)
		//           ------
		task.countUnsetBit(786, 3, 8);
	}
}

Output

 Given Num : 104
 Range : (2,5)
 Unset Bit : 3

 Given Num : 786
 Range : (3,8)
 Unset Bit : 5
/*
  Swift 4 program
  Append a set bit in given position of a number
*/
class Counting
{
	// This is counting the all inactive bits in a given range
	func countUnsetBit(_ num: Int, _ low: Int, _ high: Int)
	{
		if (num < 0 || low < 1 || high < 1 || high > 31)
		{
			return;
		}
		var i: Int = low;
		// bit counter
		var count: Int = 0;
		// Display given numbers
		print("\n Given Num : ", num, terminator: "");
		print("\n Range : (", low ,",", high ,")", terminator: "");
		// Check bits in given range
		while (i <= high && (1 << (i - 1)) <= num)
		{
			if (((1 << (i - 1)) & num) == 0)
			{
				// When the bit is inactive
				count += 1;
			}
			i += 1;
		}
		// Display calculated result
		print("\n Unset Bit : ", count );
	}
}
func main()
{
	let task: Counting = Counting();
	// Test case
	// num = 104 , low = 2, high = 5
	// 104 => (1101000)
	//           ----
	task.countUnsetBit(104, 2, 5);
	// num = 786 , low = 3, high = 8
	// 786 => (1100010010)
	//           ------
	task.countUnsetBit(786, 3, 8);
}
main();

Output

 Given Num :  104
 Range : ( 2 , 5 )
 Unset Bit :  3

 Given Num :  786
 Range : ( 3 , 8 )
 Unset Bit :  5
/*
  Kotlin program
  Append a set bit in given position of a number
*/
class Counting
{
	// This is counting the all inactive bits in a given range
	fun countUnsetBit(num: Int, low: Int, high: Int): Unit
	{
		if (num < 0 || low < 1 || high < 1 || high > 31)
		{
			return;
		}
		var i: Int = low;
		// bit counter
		var count: Int = 0;
		// Display given numbers
		print("\n Given Num : " + num);
		print("\n Range : (" + low + "," + high + ")");
		// Check bits in given range
		while (i <= high && (1 shl(i - 1)) <= num)
		{
			if (((1 shl(i - 1)) and num) == 0)
			{
				// When the bit is inactive
				count += 1;
			}
			i += 1;
		}
		// Display calculated result
		print("\n Unset Bit : " + count + "\n");
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Counting = Counting();
	// Test case
	// num = 104 , low = 2, high = 5
	// 104 => (1101000)
	//           ----
	task.countUnsetBit(104, 2, 5);
	// num = 786 , low = 3, high = 8
	// 786 => (1100010010)
	//           ------
	task.countUnsetBit(786, 3, 8);
}

Output

 Given Num : 104
 Range : (2,5)
 Unset Bit : 3

 Given Num : 786
 Range : (3,8)
 Unset Bit : 5

Time Complexity

Let's analyze the time complexity of the given algorithm. The for-loop iterates from low to high (inclusive), which means it runs high - low + 1 times. In the worst case, low is 1, and high is 31, making the loop run 31 times.

Inside the loop, there are basic operations like bitwise shifts, bitwise AND operations, and arithmetic operations, all of which can be considered constant time operations. Therefore, the overall time complexity of the algorithm is O(1) or constant time.

Resultant Output Explanation

The output of the provided C code for the given test cases is as follows:

Given Num : 104
Range     : (2,5)
Unset Bit : 3

Given Num : 786
Range     : (3,8)
Unset Bit : 5

For the first test case, num = 104, low = 2, and high = 5, the binary representation of num is (1101000). The range from position 2 to position 5 (inclusive) is 0100, which contains three inactive bits (0).

For the second test case, num = 786, low = 3, and high = 8, the binary representation of num is (1100010010). The range from position 3 to position 8 (inclusive) is 000100, which contains five inactive bits (0).

Both results are as expected and match the explanations provided earlier.

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





Categories
Relative Post