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)
    {
        Activity task = 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)
        */
        task.twoSetBits(10);
    }
}

Output

 N : 10
 3 5 6 9 10 12 17 18 20 24
// Include header file
#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()
{
	Activity task = 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) 
	*/
	task.twoSetBits(10);
	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)
	{
		Activity task = 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) 
		*/
		task.twoSetBits(10);
	}
}

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()
{
	$task = 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) 
	*/
	$task->twoSetBits(10);
}
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()
{
	var task = 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) 
	*/
	task.twoSetBits(10);
}
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() :
	task = 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) 
	
	task.twoSetBits(10)

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() 
	task = Activity.new()
	# 
	#     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) 
	
	task.twoSetBits(10)
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) 
		*/
		task.twoSetBits(10);
	}
}

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()
{
	let task: Activity = 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) 
	*/
	task.twoSetBits(10);
}
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
{
	var task: Activity = 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) 
	*/
	task.twoSetBits(10);
}

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.

New Comment