Posted on by Kalkicode
Code Bit Logic

# Print first n numbers with exactly two set bits

The given problem aims to find and print the first 'n' numbers that have exactly two set bits (bits with a value of 1) in their binary representation. In other words, we are looking for numbers where there are precisely two 1's in their binary form.

## Example

Let's consider the value of 'n' to be 10. We need to find the first ten numbers that have exactly two set bits in their binary representation.

## Algorithm

twoSetBits(n)
if n <= 0:
return
bit1 <- 1
bit2 <- 0
counter <- 0

while counter < n:
while bit2 < bit1 and counter < n:
number <- (1 << bit1) | (1 << bit2)
print number
counter <- counter + 1
bit2 <- bit2 + 1

bit1 <- bit1 + 1
bit2 <- 0
1. Start the main function.
2. Initialize the variables bit1, bit2, and counter to 1, 0, and 0, respectively.
3. Enter a loop that runs while the value of counter is less than 'n'.
4. Within this loop, enter another loop that runs while bit2 is less than bit1 and counter is less than 'n'.
5. In the inner loop, calculate the number that has exactly two set bits using the formula: ((1 << bit1) | (1 << bit2)).
6. Print the number obtained in step 5.
7. Increment bit2 and counter.
8. Exit the inner loop and increment bit1.
9. Reset bit2 to 0.
10. Repeat steps 4-9 until the value of counter becomes equal to 'n'.
11. End the main function.

## Explanation

The twoSetBits function takes an integer 'n' as input and prints the first 'n' numbers that have exactly two set bits in their binary representation. It achieves this by using two variables bit1 and bit2, which represent the positions of the two set bits in the binary number.

The outer loop runs until 'n' numbers are printed (i.e., until the counter reaches 'n'). The inner loop iterates over possible combinations of bit1 and bit2 such that bit1 is greater than bit2. This ensures that the binary number formed by setting the bits at positions bit1 and bit2 is unique.

The formula used to calculate the number with two set bits is ((1 << bit1) | (1 << bit2)). Here, 1 << bit1 and 1 << bit2 represent shifting the value 1 left by bit1 and bit2 positions, respectively, which sets the corresponding bits. The bitwise OR operation (|) combines these two numbers to form a number with two set bits.

## Code Solution

Here given code implementation process.

// C Program
// Print first n numbers with exactly two set bits
#include <stdio.h>

// Print the initial n numbers with only two active bits
void twoSetBits(int n)
{
if (n <= 0)
{
return;
}
printf("\n  N : %d \n", n);
int bit1 = 1;
int bit2 = 0;
int counter = 0;
// Execute loop until count value is less than n
while (counter < n)
{
while (bit2 < bit1 && counter < n)
{
// Display the  number which have two active bits
printf("  %d", ((1 << bit1) | (1 << bit2)));
bit2++;
// Increase resultant count
counter++;
}
bit1++;
// Reset bit two
bit2 = 0;
}
printf("\n");
}
int main()
{
/*
First few numbers which have two active bits
---------------
3   : (11)
5   : (101)
6   : (110)
9   : (1001)
10  : (1010)
12  : (1100)
17  : (10001)
18  : (10010)
20  : (10100)
24  : (11000)
33  : (100001)
34  : (100010)
36  : (100100)
40  : (101000)
48  : (110000)
65  : (1000001)
66  : (1000010)
68  : (1000100)
72  : (1001000)
80  : (1010000)
*/
// Test
twoSetBits(10);
return 0;
}

#### Output

N : 10
3  5  6  9  10  12  17  18  20  24
/*
Java Program
Print first n numbers with exactly two set bits
*/
public class Activity
{
// Print the initial n numbers with only two active bits
public void twoSetBits(int n)
{
if (n <= 0)
{
return;
}
System.out.print("\n N : " + n + " \n");
int bit1 = 1;
int bit2 = 0;
int counter = 0;
while (counter < n)
{
while (bit2 < bit1 && counter < n)
{
// Display the  number which have two active bits
System.out.print(" " + ((1 << bit1) | (1 << bit2)) );
bit2++;
counter++;
}
bit1++;
// Reset bit two
bit2 = 0;
}
System.out.print("\n");
}
public static void main(String[] args)
{

/*
First few numbers which have two active bits
---------------
3   : (11)
5   : (101)
6   : (110)
9   : (1001)
10  : (1010)
12  : (1100)
17  : (10001)
18  : (10010)
20  : (10100)
24  : (11000)
33  : (100001)
34  : (100010)
36  : (100100)
40  : (101000)
48  : (110000)
65  : (1000001)
66  : (1000010)
68  : (1000100)
72  : (1001000)
80  : (1010000)
*/
}
}

#### Output

N : 10
3 5 6 9 10 12 17 18 20 24
#include <iostream>

using namespace std;
/*
C++ Program
Print first n numbers with exactly two set bits
*/
class Activity
{
public:
// Print the initial n numbers with only two active bits
void twoSetBits(int n)
{
if (n <= 0)
{
return;
}
cout << "\n N : " << n << " \n";
int bit1 = 1;
int bit2 = 0;
int counter = 0;
while (counter < n)
{
while (bit2 < bit1 && counter < n)
{
// Display the  number which have two active bits
cout << " " << ((1 << bit1) | (1 << bit2));
bit2++;
counter++;
}
bit1++;
// Reset bit two
bit2 = 0;
}
cout << "\n";
}
};
int main()
{
/*
First few numbers which have two active bits
---------------
3   : (11)
5   : (101)
6   : (110)
9   : (1001)
10  : (1010)
12  : (1100)
17  : (10001)
18  : (10010)
20  : (10100)
24  : (11000)
33  : (100001)
34  : (100010)
36  : (100100)
40  : (101000)
48  : (110000)
65  : (1000001)
66  : (1000010)
68  : (1000100)
72  : (1001000)
80  : (1010000)
*/
return 0;
}

#### Output

N : 10
3 5 6 9 10 12 17 18 20 24
// Include namespace system
using System;
/*
C# Program
Print first n numbers with exactly two set bits
*/
public class Activity
{
// Print the initial n numbers with only two active bits
public void twoSetBits(int n)
{
if (n <= 0)
{
return;
}
Console.Write("\n N : " + n + " \n");
int bit1 = 1;
int bit2 = 0;
int counter = 0;
while (counter < n)
{
while (bit2 < bit1 && counter < n)
{
// Display the  number which have two active bits
Console.Write(" " + ((1 << bit1) | (1 << bit2)));
bit2++;
counter++;
}
bit1++;
// Reset bit two
bit2 = 0;
}
Console.Write("\n");
}
public static void Main(String[] args)
{
/*
First few numbers which have two active bits
---------------
3   : (11)
5   : (101)
6   : (110)
9   : (1001)
10  : (1010)
12  : (1100)
17  : (10001)
18  : (10010)
20  : (10100)
24  : (11000)
33  : (100001)
34  : (100010)
36  : (100100)
40  : (101000)
48  : (110000)
65  : (1000001)
66  : (1000010)
68  : (1000100)
72  : (1001000)
80  : (1010000)
*/
}
}

#### Output

N : 10
3 5 6 9 10 12 17 18 20 24
<?php
/*
Php Program
Print first n numbers with exactly two set bits
*/
class Activity
{
// Print the initial n numbers with only two active bits
public	function twoSetBits(\$n)
{
if (\$n <= 0)
{
return;
}
echo "\n N : ". \$n ." \n";
\$bit1 = 1;
\$bit2 = 0;
\$counter = 0;
while (\$counter < \$n)
{
while (\$bit2 < \$bit1 && \$counter < \$n)
{
// Display the  number which have two active bits
echo " ". ((1 << \$bit1) | (1 << \$bit2));
\$bit2++;
\$counter++;
}
\$bit1++;
// Reset bit two
\$bit2 = 0;
}
echo "\n";
}
}

function main()
{
/*
First few numbers which have two active bits
---------------
3   : (11)
5   : (101)
6   : (110)
9   : (1001)
10  : (1010)
12  : (1100)
17  : (10001)
18  : (10010)
20  : (10100)
24  : (11000)
33  : (100001)
34  : (100010)
36  : (100100)
40  : (101000)
48  : (110000)
65  : (1000001)
66  : (1000010)
68  : (1000100)
72  : (1001000)
80  : (1010000)
*/
}
main();

#### Output

N : 10
3 5 6 9 10 12 17 18 20 24
/*
Node Js Program
Print first n numbers with exactly two set bits
*/
class Activity
{
// Print the initial n numbers with only two active bits
twoSetBits(n)
{
if (n <= 0)
{
return;
}
process.stdout.write("\n N : " + n + " \n");
var bit1 = 1;
var bit2 = 0;
var counter = 0;
while (counter < n)
{
while (bit2 < bit1 && counter < n)
{
// Display the  number which have two active bits
process.stdout.write(" " + ((1 << bit1) | (1 << bit2)));
bit2++;
counter++;
}
bit1++;
// Reset bit two
bit2 = 0;
}
process.stdout.write("\n");
}
}

function main()
{
/*
First few numbers which have two active bits
---------------
3   : (11)
5   : (101)
6   : (110)
9   : (1001)
10  : (1010)
12  : (1100)
17  : (10001)
18  : (10010)
20  : (10100)
24  : (11000)
33  : (100001)
34  : (100010)
36  : (100100)
40  : (101000)
48  : (110000)
65  : (1000001)
66  : (1000010)
68  : (1000100)
72  : (1001000)
80  : (1010000)
*/
}
main();

#### Output

N : 10
3 5 6 9 10 12 17 18 20 24
#   Python 3 Program
#   Print first n numbers with exactly two set bits

class Activity :
#  Print the initial n numbers with only two active bits
def twoSetBits(self, n) :
if (n <= 0) :
return

print("\n  N : ", n ," ")
bit1 = 1
bit2 = 0
counter = 0
while (counter < n) :
while (bit2 < bit1 and counter < n) :
#  Display the  number which have two active bits
print(" ", ((1 << bit1) | (1 << bit2)), end = "")
bit2 += 1
counter += 1

bit1 += 1
#  Reset bit two
bit2 = 0

print(end = "\n")

def main() :
#
#     First few numbers which have two active bits
#     ---------------
#     3   : (11)
#     5   : (101)
#     6   : (110)
#     9   : (1001)
#     10  : (1010)
#     12  : (1100)
#     17  : (10001)
#     18  : (10010)
#     20  : (10100)
#     24  : (11000)
#     33  : (100001)
#     34  : (100010)
#     36  : (100100)
#     40  : (101000)
#     48  : (110000)
#     65  : (1000001)
#     66  : (1000010)
#     68  : (1000100)
#     72  : (1001000)
#     80  : (1010000)

if __name__ == "__main__": main()

#### Output

N :  10
3  5  6  9  10  12  17  18  20  24
#   Ruby Program
#   Print first n numbers with exactly two set bits

class Activity
#  Print the initial n numbers with only two active bits
def twoSetBits(n)
if (n <= 0)
return
end

print("\n N : ", n ," \n")
bit1 = 1
bit2 = 0
counter = 0
while (counter < n)
while (bit2 < bit1 && counter < n)
#  Display the  number which have two active bits
print(" ", ((1 << bit1) | (1 << bit2)))
bit2 += 1
counter += 1
end

bit1 += 1
#  Reset bit two
bit2 = 0
end

print("\n")
end

end

def main()
#
#     First few numbers which have two active bits
#     ---------------
#     3   : (11)
#     5   : (101)
#     6   : (110)
#     9   : (1001)
#     10  : (1010)
#     12  : (1100)
#     17  : (10001)
#     18  : (10010)
#     20  : (10100)
#     24  : (11000)
#     33  : (100001)
#     34  : (100010)
#     36  : (100100)
#     40  : (101000)
#     48  : (110000)
#     65  : (1000001)
#     66  : (1000010)
#     68  : (1000100)
#     72  : (1001000)
#     80  : (1010000)

end

main()

#### Output

N : 10
3 5 6 9 10 12 17 18 20 24
/*
Scala Program
Print first n numbers with exactly two set bits
*/
class Activity
{
// Print the initial n numbers with only two active bits
def twoSetBits(n: Int): Unit = {
if (n <= 0)
{
return;
}
print("\n N : " + n + " \n");
var bit1: Int = 1;
var bit2: Int = 0;
var counter: Int = 0;
while (counter < n)
{
while (bit2 < bit1 && counter < n)
{
// Display the  number which have two active bits
print(" " + ((1 << bit1) | (1 << bit2)));
bit2 += 1;
counter += 1;
}
bit1 += 1;
// Reset bit two
bit2 = 0;
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Activity = new Activity();
/*
First few numbers which have two active bits
---------------
3   : (11)
5   : (101)
6   : (110)
9   : (1001)
10  : (1010)
12  : (1100)
17  : (10001)
18  : (10010)
20  : (10100)
24  : (11000)
33  : (100001)
34  : (100010)
36  : (100100)
40  : (101000)
48  : (110000)
65  : (1000001)
66  : (1000010)
68  : (1000100)
72  : (1001000)
80  : (1010000)
*/
}
}

#### Output

N : 10
3 5 6 9 10 12 17 18 20 24
/*
Swift 4 Program
Print first n numbers with exactly two set bits
*/
class Activity
{
// Print the initial n numbers with only two active bits
func twoSetBits(_ n: Int)
{
if (n <= 0)
{
return;
}
print("\n N : ", n ," ");
var bit1: Int = 1;
var bit2: Int = 0;
var counter: Int = 0;
while (counter < n)
{
while (bit2 < bit1 && counter < n)
{
// Display the  number which have two active bits
print(" ", ((1 << bit1) | (1 << bit2)), terminator: "");
bit2 += 1;
counter += 1;
}
bit1 += 1;
// Reset bit two
bit2 = 0;
}
print(terminator: "\n");
}
}
func main()
{
/*
First few numbers which have two active bits
---------------
3   : (11)
5   : (101)
6   : (110)
9   : (1001)
10  : (1010)
12  : (1100)
17  : (10001)
18  : (10010)
20  : (10100)
24  : (11000)
33  : (100001)
34  : (100010)
36  : (100100)
40  : (101000)
48  : (110000)
65  : (1000001)
66  : (1000010)
68  : (1000100)
72  : (1001000)
80  : (1010000)
*/
}
main();

#### Output

N :  10
3  5  6  9  10  12  17  18  20  24
/*
Kotlin Program
Print first n numbers with exactly two set bits
*/
class Activity
{
// Print the initial n numbers with only two active bits
fun twoSetBits(n: Int): Unit
{
if (n <= 0)
{
return;
}
print("\n N : " + n + " \n");
var bit1: Int = 1;
var bit2: Int = 0;
var counter: Int = 0;
while (counter < n)
{
while (bit2 < bit1 && counter < n)
{
// Display the  number which have two active bits
print(" " + ((1 shl bit1) or (1 shl bit2)));
bit2 += 1;
counter += 1;
}
bit1 += 1;
// Reset bit two
bit2 = 0;
}
print("\n");
}
}
fun main(args: Array < String > ): Unit
{
/*
First few numbers which have two active bits
---------------
3   : (11)
5   : (101)
6   : (110)
9   : (1001)
10  : (1010)
12  : (1100)
17  : (10001)
18  : (10010)
20  : (10100)
24  : (11000)
33  : (100001)
34  : (100010)
36  : (100100)
40  : (101000)
48  : (110000)
65  : (1000001)
66  : (1000010)
68  : (1000100)
72  : (1001000)
80  : (1010000)
*/
}

#### Output

N : 10
3 5 6 9 10 12 17 18 20 24

## Output Explanation

For the given example of n = 10, the first ten numbers that have exactly two set bits are printed:

N: 10
Numbers: 3 5 6 9 10 12 17 18 20 24

## Time Complexity

The time complexity of this algorithm is O(n), where 'n' is the input number. The algorithm requires a single loop that runs 'n' times, and each iteration performs constant time operations, resulting in a linear time complexity.

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