Posted on by Kalkicode
Code Bit Logic

Print all numbers less than n which having only boundary bits are set

In this article, we will explore the problem of printing all numbers less than a given number 'n,' such that only the boundary bits are set to 1. By "boundary bits," we mean the first and last bit positions in the binary representation of the numbers. The problem can be solved efficiently using bitwise operations in C.

Problem Statement

Given a positive integer 'n,' we need to find and print all numbers less than 'n' where only the first and last bits are set to 1 in their binary representation.

Example

Let's take 'n = 300' as an example. We need to find all numbers less than 300 where only the first and last bits are set to 1.

Binary Representation

  1. 1 (Binary: 0001)
  2. 3 (Binary: 0011)
  3. 5 (Binary: 0101)
  4. 9 (Binary: 1001)
  5. 17 (Binary: 10001)
  6. 33 (Binary: 100001)
  7. 65 (Binary: 1000001)
  8. 129 (Binary: 10000001)
  9. 257 (Binary: 100000001)

Pseudocode

setBoundaryBits(num):
    n = 1
    while n < num:
        print n OR 1 (Setting the last bit to 1)
        n = n << 1 (Shift n value by 1 to the left)

Algorithm Explanation

  1. Initialize 'n' to 1.
  2. Run a loop until 'n' is less than the given number 'num.'
  3. Print the result of 'n OR 1,' which sets the last bit of 'n' to 1 while keeping all other bits the same.
  4. Left-shift 'n' by 1, i.e., 'n = n << 1,' to set the next boundary bit to 1 in the next iteration.
  5. Repeat steps 3-4 until 'n' is less than 'num.'

Here given code implementation process.

// C Program for
// Print all numbers less than n which having only boundary bits are set
#include <stdio.h>

void setBoundaryBits(int num)
{
	if (num <= 0)
	{
		return;
	}
	int n = 1;
	while (n < num)
	{
		// Display calculated result
		printf("%d\n", n | 1);
		// Shift n value by 1 to left
		n = (n << 1);
	}
}
int main(int argc, char
	const *argv[])
{
	// num     : 300 
	// ----------------
	// Number   Binary
	// 1        (1)
	// 3        (11)
	// 5        (101)
	// 9        (1001)
	// 17       (10001)
	// 33       (100001)
	// 65       (1000001)
	// 129      (10000001)
	// 257      (100000001)
	setBoundaryBits(300);
	return 0;
}

Output

1
3
5
9
17
33
65
129
257
/*
    Java Program
    Print all numbers less than n which having only boundary bits are set
*/
public class BoundaryBits
{
	public void setBoundaryBits(int num)
	{
		if (num <= 0)
		{
			return;
		}
		int n = 1;
		while (n < num)
		{
			// Display calculated result
			System.out.println(n | 1);
			// Shift n value by 1 to left
			n = (n << 1);
		}
	}
	public static void main(String[] args)
	{
		BoundaryBits task = new BoundaryBits();
		// num     : 300 
		// ----------------
		// Number   Binary
		// 1        (1)
		// 3        (11)
		// 5        (101)
		// 9        (1001)
		// 17       (10001)
		// 33       (100001)
		// 65       (1000001)
		// 129      (10000001)
		// 257      (100000001)
		task.setBoundaryBits(300);
	}
}

Output

1
3
5
9
17
33
65
129
257
// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program
    Print all numbers less than n which having only boundary bits are set
*/
class BoundaryBits
{
	public: void setBoundaryBits(int num)
	{
		if (num <= 0)
		{
			return;
		}
		int n = 1;
		while (n < num)
		{
			// Display calculated result
			cout << (n | 1) << endl;
			// Shift n value by 1 to left
			n = (n << 1);
		}
	}
};
int main()
{
	BoundaryBits *task = new BoundaryBits();
	// num     : 300 
	// ----------------
	// Number   Binary
	// 1        (1)
	// 3        (11)
	// 5        (101)
	// 9        (1001)
	// 17       (10001)
	// 33       (100001)
	// 65       (1000001)
	// 129      (10000001)
	// 257      (100000001)
	task->setBoundaryBits(300);
	return 0;
}

Output

1
3
5
9
17
33
65
129
257
// Include namespace system
using System;
/*
    Csharp Program
    Print all numbers less than n which having only boundary bits are set
*/
public class BoundaryBits
{
	public void setBoundaryBits(int num)
	{
		if (num <= 0)
		{
			return;
		}
		int n = 1;
		while (n < num)
		{
			// Display calculated result
			Console.WriteLine(n | 1);
			// Shift n value by 1 to left
			n = (n << 1);
		}
	}
	public static void Main(String[] args)
	{
		BoundaryBits task = new BoundaryBits();
		// num     : 300 
		// ----------------
		// Number   Binary
		// 1        (1)
		// 3        (11)
		// 5        (101)
		// 9        (1001)
		// 17       (10001)
		// 33       (100001)
		// 65       (1000001)
		// 129      (10000001)
		// 257      (100000001)
		task.setBoundaryBits(300);
	}
}

Output

1
3
5
9
17
33
65
129
257
package main
import "fmt"
/*
    Go Program
    Print all numbers less than n which having only boundary bits are set
*/
type BoundaryBits struct {}
func getBoundaryBits() * BoundaryBits {
	var me *BoundaryBits = &BoundaryBits {}
	return me
}
func(this BoundaryBits) setBoundaryBits(num int) {
	if num <= 0 {
		return
	}
	var n int = 1
	for (n < num) {
		// Display calculated result
		fmt.Println(n | 1)
		// Shift n value by 1 to left
		n = (n << 1)
	}
}
func main() {
	var task * BoundaryBits = getBoundaryBits()
	// num     : 300 
	// ----------------
	// Number   Binary
	// 1        (1)
	// 3        (11)
	// 5        (101)
	// 9        (1001)
	// 17       (10001)
	// 33       (100001)
	// 65       (1000001)
	// 129      (10000001)
	// 257      (100000001)
	task.setBoundaryBits(300)
}

Output

1
3
5
9
17
33
65
129
257
<?php
/*
    Php Program
    Print all numbers less than n which having only boundary bits are set
*/
class BoundaryBits
{
	public	function setBoundaryBits($num)
	{
		if ($num <= 0)
		{
			return;
		}
		$n = 1;
		while ($n < $num)
		{
			// Display calculated result
			echo(($n | 1). "\n");
			// Shift n value by 1 to left
			$n = ($n << 1);
		}
	}
}

function main()
{
	$task = new BoundaryBits();
	// num     : 300 
	// ----------------
	// Number   Binary
	// 1        (1)
	// 3        (11)
	// 5        (101)
	// 9        (1001)
	// 17       (10001)
	// 33       (100001)
	// 65       (1000001)
	// 129      (10000001)
	// 257      (100000001)
	$task->setBoundaryBits(300);
}
main();

Output

1
3
5
9
17
33
65
129
257
/*
    Node JS Program
    Print all numbers less than n which having only boundary bits are set
*/
class BoundaryBits
{
	setBoundaryBits(num)
	{
		if (num <= 0)
		{
			return;
		}
		var n = 1;
		while (n < num)
		{
			// Display calculated result
			console.log(n | 1);
			// Shift n value by 1 to left
			n = (n << 1);
		}
	}
}

function main()
{
	var task = new BoundaryBits();
	// num     : 300 
	// ----------------
	// Number   Binary
	// 1        (1)
	// 3        (11)
	// 5        (101)
	// 9        (1001)
	// 17       (10001)
	// 33       (100001)
	// 65       (1000001)
	// 129      (10000001)
	// 257      (100000001)
	task.setBoundaryBits(300);
}
main();

Output

1
3
5
9
17
33
65
129
257
#    Python 3 Program
#    Print all numbers less than n which having only boundary bits are set
class BoundaryBits :
	def setBoundaryBits(self, num) :
		if (num <= 0) :
			return
		
		n = 1
		while (n < num) :
			#  Display calculated result
			print(n | 1)
			#  Shift n value by 1 to left
			n = (n << 1)
		
	

def main() :
	task = BoundaryBits()
	#  num     : 300 
	#  ----------------
	#  Number   Binary
	#  1        (1)
	#  3        (11)
	#  5        (101)
	#  9        (1001)
	#  17       (10001)
	#  33       (100001)
	#  65       (1000001)
	#  129      (10000001)
	#  257      (100000001)
	task.setBoundaryBits(300)

if __name__ == "__main__": main()

Output

1
3
5
9
17
33
65
129
257
#    Ruby Program
#    Print all numbers less than n which having only boundary bits are set
class BoundaryBits 
	def setBoundaryBits(num) 
		if (num <= 0) 
			return
		end

		n = 1
		while (n < num) 
			#  Display calculated result
			print(n | 1, "\n")
			#  Shift n value by 1 to left
			n = (n << 1)
		end

	end

end

def main() 
	task = BoundaryBits.new()
	#  num     : 300 
	#  ----------------
	#  Number   Binary
	#  1        (1)
	#  3        (11)
	#  5        (101)
	#  9        (1001)
	#  17       (10001)
	#  33       (100001)
	#  65       (1000001)
	#  129      (10000001)
	#  257      (100000001)
	task.setBoundaryBits(300)
end

main()

Output

1
3
5
9
17
33
65
129
257
/*
    Scala Program
    Print all numbers less than n which having only boundary bits are set
*/
class BoundaryBits()
{
	def setBoundaryBits(num: Int): Unit = {
		if (num <= 0)
		{
			return;
		}
		var n: Int = 1;
		while (n < num)
		{
			// Display calculated result
			println(n | 1);
			// Shift n value by 1 to left
			n = (n << 1);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: BoundaryBits = new BoundaryBits();
		// num     : 300 
		// ----------------
		// Number   Binary
		// 1        (1)
		// 3        (11)
		// 5        (101)
		// 9        (1001)
		// 17       (10001)
		// 33       (100001)
		// 65       (1000001)
		// 129      (10000001)
		// 257      (100000001)
		task.setBoundaryBits(300);
	}
}

Output

1
3
5
9
17
33
65
129
257
/*
    Swift 4 Program
    Print all numbers less than n which having only boundary bits are set
*/
class BoundaryBits
{
	func setBoundaryBits(_ num: Int)
	{
		if (num <= 0)
		{
			return;
		}
		var n: Int = 1;
		while (n < num)
		{
			// Display calculated result
			print(n | 1);
			// Shift n value by 1 to left
			n = (n << 1);
		}
	}
}
func main()
{
	let task: BoundaryBits = BoundaryBits();
	// num     : 300 
	// ----------------
	// Number   Binary
	// 1        (1)
	// 3        (11)
	// 5        (101)
	// 9        (1001)
	// 17       (10001)
	// 33       (100001)
	// 65       (1000001)
	// 129      (10000001)
	// 257      (100000001)
	task.setBoundaryBits(300);
}
main();

Output

1
3
5
9
17
33
65
129
257
/*
    Kotlin Program
    Print all numbers less than n which having only boundary bits are set
*/
class BoundaryBits
{
	fun setBoundaryBits(num: Int): Unit
	{
		if (num <= 0)
		{
			return;
		}
		var n: Int = 1;
		while (n < num)
		{
			// Display calculated result
			println(n or 1);
			// Shift n value by 1 to left
			n = (n shl 1);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: BoundaryBits = BoundaryBits();
	// num     : 300 
	// ----------------
	// Number   Binary
	// 1        (1)
	// 3        (11)
	// 5        (101)
	// 9        (1001)
	// 17       (10001)
	// 33       (100001)
	// 65       (1000001)
	// 129      (10000001)
	// 257      (100000001)
	task.setBoundaryBits(300);
}

Output

1
3
5
9
17
33
65
129
257

Output Explanation

For the given example 'n = 300,' the code will find all numbers less than 300 that have only the first and last bits set to 1. The output will be:

1
3
5
9
17
33
65
129
257

Time Complexity

The time complexity of this code is O(log n). The loop runs until 'n' becomes greater than or equal to 'num,' and at each iteration, 'n' is left-shifted by one position, effectively doubling its value. The number of iterations required to reach 'num' can be expressed as log2(num). Therefore, the time complexity is O(log n).

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