Print all numbers whose consecutive bits are not similar
The given problem aims to find and print numbers whose consecutive bits are different. In other words, we are interested in numbers that do not have any adjacent bits with the same value in their binary representation.
Explanation with Suitable Example
Let's consider the number 42 (101010 in binary) as an example. If we observe its binary representation, we can see that there are no consecutive bits that are the same. This property makes 42 eligible for inclusion in the desired output. On the other hand, the number 7 (111 in binary) cannot be included in the output as it has consecutive similar bits (1s).
Pseudocode
To print numbers whose consecutive bits are not similar, we will use a simple algorithm. The pseudocode is as follows:
consecutiveDifferent()
n = 1
bits = 32
count = 1
while count < bits
print n
n = n << 1
if count is even
n = n + 1
count = count + 1
Explanation of Algorithm
- We initialize the variables
n
to 1,bits
to 32 (assuming 32-bit integers), andcount
to 1. - We then enter a while loop that runs until
count
is less thanbits
. - Inside the loop, we print the current value of
n
. - We left-shift the value of
n
by 1, which is equivalent to multiplying it by 2. This step ensures that we consider the next number for consecutive different bits. - If the
count
is even, we add 1 ton
. This is done to toggle the least significant bit, which ensures that there are no consecutive similar bits. - After performing the necessary operations, we increment the
count
by 1 to consider the next bit position for analysis.
Output Explanation
The given code prints a list of numbers whose consecutive bits are not similar. The output includes the first 31 such numbers (from 1 to 1431655765) that satisfy this condition. Each number is followed by a new line in the output.
Output: 1 2 5 10 21 42 85 ... 1431655765
Code Solution
Here given code implementation process.
// C Program for
// Print all numbers whose consecutive bits are not similar
#include <stdio.h>
void consecutiveDifferent()
{
int n = 1;
int bits = 32;
int count = 1;
while (count < bits)
{
// Display calculated result
printf("%d\n",n);
// Shift n value by 1 to left
n = (n << 1);
if (count % 2 == 0)
{
n += 1;
}
count++;
}
}
int main(int argc, char
const *argv[])
{
// 1 01
// 2 10
// 5 101
// 10 1010
// 21 10101
// 42 101010
// 85 1010101
// 170 10101010
// 341 101010101
// 682 1010101010
// 1365 10101010101
// 2730 101010101010
// 5461 1010101010101
// 10922 10101010101010
// 21845 101010101010101
// 43690 1010101010101010
// 87381 10101010101010101
// 174762 101010101010101010
// 349525 1010101010101010101
// 699050 10101010101010101010
// 1398101 101010101010101010101
// 2796202 1010101010101010101010
// 5592405 10101010101010101010101
// 11184810 101010101010101010101010
// 22369621 1010101010101010101010101
// 44739242 10101010101010101010101010
// 89478485 101010101010101010101010101
// 178956970 1010101010101010101010101010
// 357913941 10101010101010101010101010101
// 715827882 101010101010101010101010101010
// 1431655765 1010101010101010101010101010101
consecutiveDifferent();
return 0;
}
Output
1
2
5
10
21
42
85
170
341
682
1365
2730
5461
10922
21845
43690
87381
174762
349525
699050
1398101
2796202
5592405
11184810
22369621
44739242
89478485
178956970
357913941
715827882
1431655765
/*
Java Program
Print all numbers whose consecutive bits are not similar
*/
public class BinaryBits
{
public void consecutiveDifferent()
{
int n = 1;
int bits = 32;
int count = 1;
while (count < bits)
{
// Display calculated result
System.out.println(n);
// Shift n value by 1 to left
n = (n << 1);
if (count % 2 == 0)
{
n += 1;
}
count++;
}
}
public static void main(String[] args)
{
BinaryBits task = new BinaryBits();
// 1 01
// 2 10
// 5 101
// 10 1010
// 21 10101
// 42 101010
// 85 1010101
// 170 10101010
// 341 101010101
// 682 1010101010
// 1365 10101010101
// 2730 101010101010
// 5461 1010101010101
// 10922 10101010101010
// 21845 101010101010101
// 43690 1010101010101010
// 87381 10101010101010101
// 174762 101010101010101010
// 349525 1010101010101010101
// 699050 10101010101010101010
// 1398101 101010101010101010101
// 2796202 1010101010101010101010
// 5592405 10101010101010101010101
// 11184810 101010101010101010101010
// 22369621 1010101010101010101010101
// 44739242 10101010101010101010101010
// 89478485 101010101010101010101010101
// 178956970 1010101010101010101010101010
// 357913941 10101010101010101010101010101
// 715827882 101010101010101010101010101010
// 1431655765 1010101010101010101010101010101
task.consecutiveDifferent();
}
}
Output
1
2
5
10
21
42
85
170
341
682
1365
2730
5461
10922
21845
43690
87381
174762
349525
699050
1398101
2796202
5592405
11184810
22369621
44739242
89478485
178956970
357913941
715827882
1431655765
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Print all numbers whose consecutive bits are not similar
*/
class BinaryBits
{
public: void consecutiveDifferent()
{
int n = 1;
int bits = 32;
int count = 1;
while (count < bits)
{
// Display calculated result
cout << n << endl;
// Shift n value by 1 to left
n = (n << 1);
if (count % 2 == 0)
{
n += 1;
}
count++;
}
}
};
int main()
{
BinaryBits *task = new BinaryBits();
// 1 01
// 2 10
// 5 101
// 10 1010
// 21 10101
// 42 101010
// 85 1010101
// 170 10101010
// 341 101010101
// 682 1010101010
// 1365 10101010101
// 2730 101010101010
// 5461 1010101010101
// 10922 10101010101010
// 21845 101010101010101
// 43690 1010101010101010
// 87381 10101010101010101
// 174762 101010101010101010
// 349525 1010101010101010101
// 699050 10101010101010101010
// 1398101 101010101010101010101
// 2796202 1010101010101010101010
// 5592405 10101010101010101010101
// 11184810 101010101010101010101010
// 22369621 1010101010101010101010101
// 44739242 10101010101010101010101010
// 89478485 101010101010101010101010101
// 178956970 1010101010101010101010101010
// 357913941 10101010101010101010101010101
// 715827882 101010101010101010101010101010
// 1431655765 1010101010101010101010101010101
task->consecutiveDifferent();
return 0;
}
Output
1
2
5
10
21
42
85
170
341
682
1365
2730
5461
10922
21845
43690
87381
174762
349525
699050
1398101
2796202
5592405
11184810
22369621
44739242
89478485
178956970
357913941
715827882
1431655765
// Include namespace system
using System;
/*
Csharp Program
Print all numbers whose consecutive bits are not similar
*/
public class BinaryBits
{
public void consecutiveDifferent()
{
int n = 1;
int bits = 32;
int count = 1;
while (count < bits)
{
// Display calculated result
Console.WriteLine(n);
// Shift n value by 1 to left
n = (n << 1);
if (count % 2 == 0)
{
n += 1;
}
count++;
}
}
public static void Main(String[] args)
{
BinaryBits task = new BinaryBits();
// 1 01
// 2 10
// 5 101
// 10 1010
// 21 10101
// 42 101010
// 85 1010101
// 170 10101010
// 341 101010101
// 682 1010101010
// 1365 10101010101
// 2730 101010101010
// 5461 1010101010101
// 10922 10101010101010
// 21845 101010101010101
// 43690 1010101010101010
// 87381 10101010101010101
// 174762 101010101010101010
// 349525 1010101010101010101
// 699050 10101010101010101010
// 1398101 101010101010101010101
// 2796202 1010101010101010101010
// 5592405 10101010101010101010101
// 11184810 101010101010101010101010
// 22369621 1010101010101010101010101
// 44739242 10101010101010101010101010
// 89478485 101010101010101010101010101
// 178956970 1010101010101010101010101010
// 357913941 10101010101010101010101010101
// 715827882 101010101010101010101010101010
// 1431655765 1010101010101010101010101010101
task.consecutiveDifferent();
}
}
Output
1
2
5
10
21
42
85
170
341
682
1365
2730
5461
10922
21845
43690
87381
174762
349525
699050
1398101
2796202
5592405
11184810
22369621
44739242
89478485
178956970
357913941
715827882
1431655765
package main
import "fmt"
/*
Go Program
Print all numbers whose consecutive bits are not similar
*/
type BinaryBits struct {}
func getBinaryBits() * BinaryBits {
var me *BinaryBits = &BinaryBits {}
return me
}
func(this BinaryBits) consecutiveDifferent() {
var n int = 1
var bits int = 32
var count int = 1
for (count < bits) {
// Display calculated result
fmt.Println(n)
// Shift n value by 1 to left
n = (n << 1)
if count % 2 == 0 {
n += 1
}
count++
}
}
func main() {
var task * BinaryBits = getBinaryBits()
// 1 01
// 2 10
// 5 101
// 10 1010
// 21 10101
// 42 101010
// 85 1010101
// 170 10101010
// 341 101010101
// 682 1010101010
// 1365 10101010101
// 2730 101010101010
// 5461 1010101010101
// 10922 10101010101010
// 21845 101010101010101
// 43690 1010101010101010
// 87381 10101010101010101
// 174762 101010101010101010
// 349525 1010101010101010101
// 699050 10101010101010101010
// 1398101 101010101010101010101
// 2796202 1010101010101010101010
// 5592405 10101010101010101010101
// 11184810 101010101010101010101010
// 22369621 1010101010101010101010101
// 44739242 10101010101010101010101010
// 89478485 101010101010101010101010101
// 178956970 1010101010101010101010101010
// 357913941 10101010101010101010101010101
// 715827882 101010101010101010101010101010
// 1431655765 1010101010101010101010101010101
task.consecutiveDifferent()
}
Output
1
2
5
10
21
42
85
170
341
682
1365
2730
5461
10922
21845
43690
87381
174762
349525
699050
1398101
2796202
5592405
11184810
22369621
44739242
89478485
178956970
357913941
715827882
1431655765
<?php
/*
Php Program
Print all numbers whose consecutive bits are not similar
*/
class BinaryBits
{
public function consecutiveDifferent()
{
$n = 1;
$bits = 32;
$count = 1;
while ($count < $bits)
{
// Display calculated result
echo($n.
"\n");
// Shift n value by 1 to left
$n = ($n << 1);
if ($count % 2 == 0)
{
$n += 1;
}
$count++;
}
}
}
function main()
{
$task = new BinaryBits();
// 1 01
// 2 10
// 5 101
// 10 1010
// 21 10101
// 42 101010
// 85 1010101
// 170 10101010
// 341 101010101
// 682 1010101010
// 1365 10101010101
// 2730 101010101010
// 5461 1010101010101
// 10922 10101010101010
// 21845 101010101010101
// 43690 1010101010101010
// 87381 10101010101010101
// 174762 101010101010101010
// 349525 1010101010101010101
// 699050 10101010101010101010
// 1398101 101010101010101010101
// 2796202 1010101010101010101010
// 5592405 10101010101010101010101
// 11184810 101010101010101010101010
// 22369621 1010101010101010101010101
// 44739242 10101010101010101010101010
// 89478485 101010101010101010101010101
// 178956970 1010101010101010101010101010
// 357913941 10101010101010101010101010101
// 715827882 101010101010101010101010101010
// 1431655765 1010101010101010101010101010101
$task->consecutiveDifferent();
}
main();
Output
1
2
5
10
21
42
85
170
341
682
1365
2730
5461
10922
21845
43690
87381
174762
349525
699050
1398101
2796202
5592405
11184810
22369621
44739242
89478485
178956970
357913941
715827882
1431655765
/*
Node JS Program
Print all numbers whose consecutive bits are not similar
*/
class BinaryBits
{
consecutiveDifferent()
{
var n = 1;
var bits = 32;
var count = 1;
while (count < bits)
{
// Display calculated result
console.log(n);
// Shift n value by 1 to left
n = (n << 1);
if (count % 2 == 0)
{
n += 1;
}
count++;
}
}
}
function main()
{
var task = new BinaryBits();
// 1 01
// 2 10
// 5 101
// 10 1010
// 21 10101
// 42 101010
// 85 1010101
// 170 10101010
// 341 101010101
// 682 1010101010
// 1365 10101010101
// 2730 101010101010
// 5461 1010101010101
// 10922 10101010101010
// 21845 101010101010101
// 43690 1010101010101010
// 87381 10101010101010101
// 174762 101010101010101010
// 349525 1010101010101010101
// 699050 10101010101010101010
// 1398101 101010101010101010101
// 2796202 1010101010101010101010
// 5592405 10101010101010101010101
// 11184810 101010101010101010101010
// 22369621 1010101010101010101010101
// 44739242 10101010101010101010101010
// 89478485 101010101010101010101010101
// 178956970 1010101010101010101010101010
// 357913941 10101010101010101010101010101
// 715827882 101010101010101010101010101010
// 1431655765 1010101010101010101010101010101
task.consecutiveDifferent();
}
main();
Output
1
2
5
10
21
42
85
170
341
682
1365
2730
5461
10922
21845
43690
87381
174762
349525
699050
1398101
2796202
5592405
11184810
22369621
44739242
89478485
178956970
357913941
715827882
1431655765
# Python 3 Program
# Print all numbers whose consecutive bits are not similar
class BinaryBits :
def consecutiveDifferent(self) :
n = 1
bits = 32
count = 1
while (count < bits) :
# Display calculated result
print(n)
# Shift n value by 1 to left
n = (n << 1)
if (count % 2 == 0) :
n += 1
count += 1
def main() :
task = BinaryBits()
# 1 01
# 2 10
# 5 101
# 10 1010
# 21 10101
# 42 101010
# 85 1010101
# 170 10101010
# 341 101010101
# 682 1010101010
# 1365 10101010101
# 2730 101010101010
# 5461 1010101010101
# 10922 10101010101010
# 21845 101010101010101
# 43690 1010101010101010
# 87381 10101010101010101
# 174762 101010101010101010
# 349525 1010101010101010101
# 699050 10101010101010101010
# 1398101 101010101010101010101
# 2796202 1010101010101010101010
# 5592405 10101010101010101010101
# 11184810 101010101010101010101010
# 22369621 1010101010101010101010101
# 44739242 10101010101010101010101010
# 89478485 101010101010101010101010101
# 178956970 1010101010101010101010101010
# 357913941 10101010101010101010101010101
# 715827882 101010101010101010101010101010
# 1431655765 1010101010101010101010101010101
task.consecutiveDifferent()
if __name__ == "__main__": main()
Output
1
2
5
10
21
42
85
170
341
682
1365
2730
5461
10922
21845
43690
87381
174762
349525
699050
1398101
2796202
5592405
11184810
22369621
44739242
89478485
178956970
357913941
715827882
1431655765
# Ruby Program
# Print all numbers whose consecutive bits are not similar
class BinaryBits
def consecutiveDifferent()
n = 1
bits = 32
count = 1
while (count < bits)
# Display calculated result
print(n, "\n")
# Shift n value by 1 to left
n = (n << 1)
if (count % 2 == 0)
n += 1
end
count += 1
end
end
end
def main()
task = BinaryBits.new()
# 1 01
# 2 10
# 5 101
# 10 1010
# 21 10101
# 42 101010
# 85 1010101
# 170 10101010
# 341 101010101
# 682 1010101010
# 1365 10101010101
# 2730 101010101010
# 5461 1010101010101
# 10922 10101010101010
# 21845 101010101010101
# 43690 1010101010101010
# 87381 10101010101010101
# 174762 101010101010101010
# 349525 1010101010101010101
# 699050 10101010101010101010
# 1398101 101010101010101010101
# 2796202 1010101010101010101010
# 5592405 10101010101010101010101
# 11184810 101010101010101010101010
# 22369621 1010101010101010101010101
# 44739242 10101010101010101010101010
# 89478485 101010101010101010101010101
# 178956970 1010101010101010101010101010
# 357913941 10101010101010101010101010101
# 715827882 101010101010101010101010101010
# 1431655765 1010101010101010101010101010101
task.consecutiveDifferent()
end
main()
Output
1
2
5
10
21
42
85
170
341
682
1365
2730
5461
10922
21845
43690
87381
174762
349525
699050
1398101
2796202
5592405
11184810
22369621
44739242
89478485
178956970
357913941
715827882
1431655765
/*
Scala Program
Print all numbers whose consecutive bits are not similar
*/
class BinaryBits()
{
def consecutiveDifferent(): Unit = {
var n: Int = 1;
var bits: Int = 32;
var count: Int = 1;
while (count < bits)
{
// Display calculated result
println(n);
// Shift n value by 1 to left
n = (n << 1);
if (count % 2 == 0)
{
n += 1;
}
count += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: BinaryBits = new BinaryBits();
// 1 01
// 2 10
// 5 101
// 10 1010
// 21 10101
// 42 101010
// 85 1010101
// 170 10101010
// 341 101010101
// 682 1010101010
// 1365 10101010101
// 2730 101010101010
// 5461 1010101010101
// 10922 10101010101010
// 21845 101010101010101
// 43690 1010101010101010
// 87381 10101010101010101
// 174762 101010101010101010
// 349525 1010101010101010101
// 699050 10101010101010101010
// 1398101 101010101010101010101
// 2796202 1010101010101010101010
// 5592405 10101010101010101010101
// 11184810 101010101010101010101010
// 22369621 1010101010101010101010101
// 44739242 10101010101010101010101010
// 89478485 101010101010101010101010101
// 178956970 1010101010101010101010101010
// 357913941 10101010101010101010101010101
// 715827882 101010101010101010101010101010
// 1431655765 1010101010101010101010101010101
task.consecutiveDifferent();
}
}
Output
1
2
5
10
21
42
85
170
341
682
1365
2730
5461
10922
21845
43690
87381
174762
349525
699050
1398101
2796202
5592405
11184810
22369621
44739242
89478485
178956970
357913941
715827882
1431655765
/*
Swift 4 Program
Print all numbers whose consecutive bits are not similar
*/
class BinaryBits
{
func consecutiveDifferent()
{
var n: Int = 1;
let bits: Int = 32;
var count: Int = 1;
while (count < bits)
{
// Display calculated result
print(n);
// Shift n value by 1 to left
n = (n << 1);
if (count % 2 == 0)
{
n += 1;
}
count += 1;
}
}
}
func main()
{
let task: BinaryBits = BinaryBits();
// 1 01
// 2 10
// 5 101
// 10 1010
// 21 10101
// 42 101010
// 85 1010101
// 170 10101010
// 341 101010101
// 682 1010101010
// 1365 10101010101
// 2730 101010101010
// 5461 1010101010101
// 10922 10101010101010
// 21845 101010101010101
// 43690 1010101010101010
// 87381 10101010101010101
// 174762 101010101010101010
// 349525 1010101010101010101
// 699050 10101010101010101010
// 1398101 101010101010101010101
// 2796202 1010101010101010101010
// 5592405 10101010101010101010101
// 11184810 101010101010101010101010
// 22369621 1010101010101010101010101
// 44739242 10101010101010101010101010
// 89478485 101010101010101010101010101
// 178956970 1010101010101010101010101010
// 357913941 10101010101010101010101010101
// 715827882 101010101010101010101010101010
// 1431655765 1010101010101010101010101010101
task.consecutiveDifferent();
}
main();
Output
1
2
5
10
21
42
85
170
341
682
1365
2730
5461
10922
21845
43690
87381
174762
349525
699050
1398101
2796202
5592405
11184810
22369621
44739242
89478485
178956970
357913941
715827882
1431655765
/*
Kotlin Program
Print all numbers whose consecutive bits are not similar
*/
class BinaryBits
{
fun consecutiveDifferent(): Unit
{
var n: Int = 1;
val bits: Int = 32;
var count: Int = 1;
while (count < bits)
{
// Display calculated result
println(n);
// Shift n value by 1 to left
n = (n shl 1);
if (count % 2 == 0)
{
n += 1;
}
count += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val task: BinaryBits = BinaryBits();
// 1 01
// 2 10
// 5 101
// 10 1010
// 21 10101
// 42 101010
// 85 1010101
// 170 10101010
// 341 101010101
// 682 1010101010
// 1365 10101010101
// 2730 101010101010
// 5461 1010101010101
// 10922 10101010101010
// 21845 101010101010101
// 43690 1010101010101010
// 87381 10101010101010101
// 174762 101010101010101010
// 349525 1010101010101010101
// 699050 10101010101010101010
// 1398101 101010101010101010101
// 2796202 1010101010101010101010
// 5592405 10101010101010101010101
// 11184810 101010101010101010101010
// 22369621 1010101010101010101010101
// 44739242 10101010101010101010101010
// 89478485 101010101010101010101010101
// 178956970 1010101010101010101010101010
// 357913941 10101010101010101010101010101
// 715827882 101010101010101010101010101010
// 1431655765 1010101010101010101010101010101
task.consecutiveDifferent();
}
Output
1
2
5
10
21
42
85
170
341
682
1365
2730
5461
10922
21845
43690
87381
174762
349525
699050
1398101
2796202
5592405
11184810
22369621
44739242
89478485
178956970
357913941
715827882
1431655765
Time Complexity
The time complexity of the provided code is O(bits), where bits
is the number of bits used to represent
an integer. In this case, since the integers are represented using 32 bits (as per the code), the time complexity is
O(32) or simply O(1). This is because the while loop will iterate 31 times, performing a constant number of
operations in each iteration.
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