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)
{
// Test case
// num = 104 , low = 2, high = 5
// 104 => (1101000)
//           ----
// num = 786 , low = 3, high = 8
// 786 => (1100010010)
//           ------
}
}``````

#### 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()
{
// Test case
// num = 104 , low = 2, high = 5
// 104 => (1101000)
//           ----
// num = 786 , low = 3, high = 8
// 786 => (1100010010)
//           ------
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)
{
// Test case
// num = 104 , low = 2, high = 5
// 104 => (1101000)
//           ----
// num = 786 , low = 3, high = 8
// 786 => (1100010010)
//           ------
}
}``````

#### 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()
{
// Test case
// num = 104 , low = 2, high = 5
// 104 => (1101000)
//           ----
// num = 786 , low = 3, high = 8
// 786 => (1100010010)
//           ------
}
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()
{
// Test case
// num = 104 , low = 2, high = 5
// 104 => (1101000)
//           ----
// num = 786 , low = 3, high = 8
// 786 => (1100010010)
//           ------
}
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() :
#  Test case
#  num = 104 , low = 2, high = 5
#  104 => (1101000)
#            ----
#  num = 786 , low = 3, high = 8
#  786 => (1100010010)
#            ------

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()
#  Test case
#  num = 104 , low = 2, high = 5
#  104 => (1101000)
#            ----
#  num = 786 , low = 3, high = 8
#  786 => (1100010010)
#            ------
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)
//           ----
// num = 786 , low = 3, high = 8
// 786 => (1100010010)
//           ------
}
}``````

#### 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()
{
// Test case
// num = 104 , low = 2, high = 5
// 104 => (1101000)
//           ----
// num = 786 , low = 3, high = 8
// 786 => (1100010010)
//           ------
}
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
{
// Test case
// num = 104 , low = 2, high = 5
// 104 => (1101000)
//           ----
// num = 786 , low = 3, high = 8
// 786 => (1100010010)
//           ------
}``````

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

Categories
Relative Post