Skip to main content

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

  1. We initialize the variables n to 1, bits to 32 (assuming 32-bit integers), and count to 1.
  2. We then enter a while loop that runs until count is less than bits.
  3. Inside the loop, we print the current value of n.
  4. 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.
  5. If the count is even, we add 1 to n. This is done to toggle the least significant bit, which ensures that there are no consecutive similar bits.
  6. 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.

Last updated on by Kalkicode




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