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:
num = 104
, represented as(1101000)
in binary.num = 786
, represented as(1100010010)
in binary.
We will perform two queries in this example:
low = 2
andhigh = 5
fornum = 104
.low = 3
andhigh = 8
fornum = 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:
- Input the positive integer
num
, and the range boundarieslow
andhigh
. - Check if the input is valid, i.e., if
num
is positive andlow
andhigh
are within the valid range (1 to 31). - Initialize a variable
count
to 0, which will keep track of the number of unset bits within the specified range. - Iterate from
low
tohigh
(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.
- Check if the bit at the current position is unset (0) in the binary representation of
- 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.
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