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)
{
// num     : 300
// ----------------
// Number   Binary
// 1        (1)
// 3        (11)
// 5        (101)
// 9        (1001)
// 17       (10001)
// 33       (100001)
// 65       (1000001)
// 129      (10000001)
// 257      (100000001)
}
}``````

#### 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()
{
// num     : 300
// ----------------
// Number   Binary
// 1        (1)
// 3        (11)
// 5        (101)
// 9        (1001)
// 17       (10001)
// 33       (100001)
// 65       (1000001)
// 129      (10000001)
// 257      (100000001)
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)
{
// num     : 300
// ----------------
// Number   Binary
// 1        (1)
// 3        (11)
// 5        (101)
// 9        (1001)
// 17       (10001)
// 33       (100001)
// 65       (1000001)
// 129      (10000001)
// 257      (100000001)
}
}``````

#### 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)
}``````

#### 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()
{
// num     : 300
// ----------------
// Number   Binary
// 1        (1)
// 3        (11)
// 5        (101)
// 9        (1001)
// 17       (10001)
// 33       (100001)
// 65       (1000001)
// 129      (10000001)
// 257      (100000001)
}
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()
{
// num     : 300
// ----------------
// Number   Binary
// 1        (1)
// 3        (11)
// 5        (101)
// 9        (1001)
// 17       (10001)
// 33       (100001)
// 65       (1000001)
// 129      (10000001)
// 257      (100000001)
}
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() :
#  num     : 300
#  ----------------
#  Number   Binary
#  1        (1)
#  3        (11)
#  5        (101)
#  9        (1001)
#  17       (10001)
#  33       (100001)
#  65       (1000001)
#  129      (10000001)
#  257      (100000001)

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()
#  num     : 300
#  ----------------
#  Number   Binary
#  1        (1)
#  3        (11)
#  5        (101)
#  9        (1001)
#  17       (10001)
#  33       (100001)
#  65       (1000001)
#  129      (10000001)
#  257      (100000001)
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)
}
}``````

#### 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()
{
// num     : 300
// ----------------
// Number   Binary
// 1        (1)
// 3        (11)
// 5        (101)
// 9        (1001)
// 17       (10001)
// 33       (100001)
// 65       (1000001)
// 129      (10000001)
// 257      (100000001)
}
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
{
// num     : 300
// ----------------
// Number   Binary
// 1        (1)
// 3        (11)
// 5        (101)
// 9        (1001)
// 17       (10001)
// 33       (100001)
// 65       (1000001)
// 129      (10000001)
// 257      (100000001)
}``````

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

Categories
Relative Post