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 (Binary: 0001)
- 3 (Binary: 0011)
- 5 (Binary: 0101)
- 9 (Binary: 1001)
- 17 (Binary: 10001)
- 33 (Binary: 100001)
- 65 (Binary: 1000001)
- 129 (Binary: 10000001)
- 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
- Initialize 'n' to 1.
- Run a loop until 'n' is less than the given number 'num.'
- Print the result of 'n OR 1,' which sets the last bit of 'n' to 1 while keeping all other bits the same.
- Left-shift 'n' by 1, i.e., 'n = n << 1,' to set the next boundary bit to 1 in the next iteration.
- 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
257package 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
257Output 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).
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