Posted on by Kalkicode
Code Bit Logic

# Check if a number has bits in alternate pattern

The given problem is to check if a given number has bits in an alternate pattern. In an alternate pattern, adjacent bits have different values (0 and 1) from each other. For example, the binary representation of the number 85 is 1010101, which has alternating bits (1s and 0s). On the other hand, the binary representation of the number 106 is 1101010, which does not have alternating bits.

Explanation with Suitable Example:

Let's take the number 85 as an example to illustrate how the algorithm works:

1. Step 1: Initialize the number `num` to 85 (binary: 1010101).
2. Step 2: Start with a result indicator (`result`) set to 1, which means we assume the number has alternating bits until we find a contradiction.
3. Step 3: Get the last bit of the number `n` by performing a bitwise AND operation with 1 (`back = n & 1`). Here, `back` will be 1 as the last bit of 85 is 1.
4. Step 4: Right shift the number `n` by one (`n = n >> 1`). Now, `n` becomes 42 (binary: 101010).
5. Step 5: Compare the current last bit of `n` with the value of `back`. If they are the same, it means two consecutive bits are the same, and the result indicator (`result`) is set to 0 (meaning the number does not have an alternate pattern). Otherwise, update `back` to the current last bit of `n`.
6. Step 6: Continue the process by right-shifting `n` until it becomes 0 or until we find two consecutive bits that are the same.

In this case, after executing the loop, we find that the `result` remains 1, indicating that all bits in the number are in an alternate pattern.

Standard Pseudocode:

``````Procedure alternatePattern(num)
if num <= 0 then
return
end if

n <- num
result <- 1
back <- n & 1
n <- n >> 1

while n > 0 AND result = 1 do
if (n & 1) = back then
result <- 0
else
back <- n & 1
end if
n <- n >> 1
end while

print "Number :", num
if result = 0 then
print "No"
else
print "Yes"
end if
End Procedure
``````

Algorithm Explanation:

1. Start by checking if the input number (`num`) is less than or equal to 0. If it is, return from the function since negative numbers and zero do not have a valid binary representation with alternating bits.

2. Initialize variables `n` and `result`. `n` is a temporary copy of the input number `num`, and `result` is the indicator variable set to 1, assuming the number has alternating bits until proven otherwise.

3. Extract the last bit of the number `n` using a bitwise AND operation with 1 and store it in `back`.

4. Right shift `n` by one position to get the next bit for comparison.

5. Enter a loop that continues until `n` becomes 0 or until we find two consecutive bits that are the same (resulting in `result` becoming 0).

6. Inside the loop, compare the current last bit of `n` with the value of `back`. If they are the same, it means two consecutive bits are the same, and we set `result` to 0, indicating that the number does not have an alternate pattern. Otherwise, update `back` to the current last bit of `n` for the next iteration.

7. Right shift `n` by one position to process the next bit.

8. Once the loop finishes, print the original number `num` and whether it has an alternate pattern (`Yes`) or not (`No`) based on the value of the `result` variable.

## Code Solution

Here given code implementation process.

``````// C program
// Check if a number has bits in alternate pattern
#include <stdio.h>

// Check that bit pair are different in given number or not
void alternatePattern(int num)
{
if (num <= 0)
{
return;
}
// Get given number
int n = num;
// Result indicator
int result = 1;
// Get last bit
int back = n & 1;
// left shift by one
n = n >> 1;
// Execute loop until
while (n > 0 && result == 1)
{
if ((n & 1) == back)
{
// When two consecutive bits are same
result = 0;
}
else
{
back = n & 1;
}
n = n >> 1;
}
// Display given number
printf("\n Number : %d", num);
if (result == 0)
{
printf("\n No");
}
else
{
printf("\n Yes");
}
}
int main(int argc, char
const *argv[])
{
int num = 85;
// 85 (1010101)
alternatePattern(num);
num = 42;
// 42 (101010)
alternatePattern(num);
num = 106;
// 106 (1101010)
alternatePattern(num);
num = 2;
// 2 (10)
alternatePattern(num);
num = 22;
// 22 (10110)
alternatePattern(num);
return 0;
}``````

#### Output

`````` Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No``````
``````/*
Java program
Check if a number has bits in alternate pattern
*/
public class Sequence
{
// Check that bit pair are different in given number or not
public void alternatePattern(int num)
{
if (num <= 0)
{
return;
}
// Get given number
int n = num;
// Result indicator
boolean result = true;
// Get last bit
int back = n & 1;
// left shift by one
n = n >> 1;
// Execute loop until
while (n > 0 && result == true)
{
if ((n & 1) == back)
{
// When two consecutive bits are same
result = false;
}
else
{
back = n & 1;
}
n = n >> 1;
}
// Display given number
System.out.print("\n Number : " + num );
if (result == false)
{
System.out.print("\n No");
}
else
{
System.out.print("\n Yes");
}
}

public static void main(String[] args)
{
int num = 85;
// 85 (1010101)
num = 42;
// 42 (101010)
num = 106;
// 106 (1101010)
num = 2;
// 2 (10)
num = 22;
// 22 (10110)
}
}``````

#### Output

`````` Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No``````
``````// Include namespace system
using System;
/*
C# program
Check if a number has bits in alternate pattern
*/
public class Sequence
{
// Check that bit pair are different in given number or not
public void alternatePattern(int num)
{
if (num <= 0)
{
return;
}
// Get given number
int n = num;
// Result indicator
int result = 1;
// Get last bit
int back = n & 1;
// left shift by one
n = n >> 1;
// Execute loop until
while (n > 0 && result == 1)
{
if ((n & 1) == back)
{
// When two consecutive bits are same
result = 0;
}
else
{
back = n & 1;
}
n = n >> 1;
}
// Display given number
Console.Write("\n Number : " + num);
if (result == 0)
{
Console.Write("\n No");
}
else
{
Console.Write("\n Yes");
}
}
public static void Main(String[] args)
{
int num = 85;
// 85 (1010101)
num = 42;
// 42 (101010)
num = 106;
// 106 (1101010)
num = 2;
// 2 (10)
num = 22;
// 22 (10110)
}
}``````

#### Output

`````` Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ program
Check if a number has bits in alternate pattern
*/
class Sequence
{
public:
// Check that bit pair are different in given number or not
void alternatePattern(int num)
{
if (num <= 0)
{
return;
}
// Get given number
int n = num;
// Result indicator
int result = 1;
// Get last bit
int back = n &1;
// left shift by one
n = n >> 1;
// Execute loop until
while (n > 0 && result == 1)
{
if ((n &1) == back)
{
// When two consecutive bits are same
result = 0;
}
else
{
back = n &1;
}
n = n >> 1;
}
// Display given number
cout << "\n Number : " << num;
if (result == 0)
{
cout << "\n No";
}
else
{
cout << "\n Yes";
}
}
};
int main()
{
int num = 85;
// 85 (1010101)
num = 42;
// 42 (101010)
num = 106;
// 106 (1101010)
num = 2;
// 2 (10)
num = 22;
// 22 (10110)
return 0;
}``````

#### Output

`````` Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No``````
``````<?php
/*
Php program
Check if a number has bits in alternate pattern
*/
class Sequence
{
// Check that bit pair are different in given number or not
public	function alternatePattern(\$num)
{
if (\$num <= 0)
{
return;
}
// Get given number
\$n = \$num;
// Result indicator
\$result = 1;
// Get last bit
\$back = \$n & 1;
// left shift by one
\$n = \$n >> 1;
// Execute loop until
while (\$n > 0 && \$result == 1)
{
if ((\$n & 1) == \$back)
{
// When two consecutive bits are same
\$result = 0;
}
else
{
\$back = \$n & 1;
}
\$n = \$n >> 1;
}
// Display given number
echo "\n Number : ". \$num;
if (\$result == 0)
{
echo "\n No";
}
else
{
echo "\n Yes";
}
}
}

function main()
{
\$num = 85;
// 85 (1010101)
\$num = 42;
// 42 (101010)
\$num = 106;
// 106 (1101010)
\$num = 2;
// 2 (10)
\$num = 22;
// 22 (10110)
}
main();``````

#### Output

`````` Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No``````
``````/*
Node Js program
Check if a number has bits in alternate pattern
*/
class Sequence
{
// Check that bit pair are different in given number or not
alternatePattern(num)
{
if (num <= 0)
{
return;
}
// Get given number
var n = num;
// Result indicator
var result = 1;
// Get last bit
var back = n & 1;
// left shift by one
n = n >> 1;
// Execute loop until
while (n > 0 && result == 1)
{
if ((n & 1) == back)
{
// When two consecutive bits are same
result = 0;
}
else
{
back = n & 1;
}
n = n >> 1;
}
// Display given number
process.stdout.write("\n Number : " + num);
if (result == 0)
{
process.stdout.write("\n No");
}
else
{
process.stdout.write("\n Yes");
}
}
}

function main()
{
var num = 85;
// 85 (1010101)
num = 42;
// 42 (101010)
num = 106;
// 106 (1101010)
num = 2;
// 2 (10)
num = 22;
// 22 (10110)
}
main();``````

#### Output

`````` Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No``````
``````#   Python 3 program
#   Check if a number has bits in alternate pattern

class Sequence :
#  Check that bit pair are different in given number or not
def alternatePattern(self, num) :
if (num <= 0) :
return

#  Get given number
n = num
#  Result indicator
result = 1
#  Get last bit
back = n & 1
#  left shift by one
n = n >> 1
#  Execute loop until
while (n > 0 and result == 1) :
if ((n & 1) == back) :
#  When two consecutive bits are same
result = 0
else :
back = n & 1

n = n >> 1

#  Display given number
print("\n Number : ", num, end = "")
if (result == 0) :
print("\n No", end = "")
else :
print("\n Yes", end = "")

def main() :
num = 85
#  85 (1010101)
num = 42
#  42 (101010)
num = 106
#  106 (1101010)
num = 2
#  2 (10)
num = 22
#  22 (10110)

if __name__ == "__main__": main()``````

#### Output

`````` Number :  85
Yes
Number :  42
Yes
Number :  106
No
Number :  2
Yes
Number :  22
No``````
``````#   Ruby program
#   Check if a number has bits in alternate pattern

class Sequence
#  Check that bit pair are different in given number or not
def alternatePattern(num)
if (num <= 0)
return
end

#  Get given number
n = num
#  Result indicator
result = 1
#  Get last bit
back = n & 1
#  left shift by one
n = n >> 1
#  Execute loop until
while (n > 0 && result == 1)
if ((n & 1) == back)
#  When two consecutive bits are same
result = 0
else
back = n & 1
end

n = n >> 1
end

#  Display given number
print("\n Number : ", num)
if (result == 0)
print("\n No")
else
print("\n Yes")
end

end

end

def main()
num = 85
#  85 (1010101)
num = 42
#  42 (101010)
num = 106
#  106 (1101010)
num = 2
#  2 (10)
num = 22
#  22 (10110)
end

main()``````

#### Output

`````` Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No``````
``````/*
Scala program
Check if a number has bits in alternate pattern
*/
class Sequence
{
// Check that bit pair are different in given number or not
def alternatePattern(num: Int): Unit = {
if (num <= 0)
{
return;
}
// Get given number
var n: Int = num;
// Result indicator
var result: Int = 1;
// Get last bit
var back: Int = n & 1;
// left shift by one
n = n >> 1;
// Execute loop until
while (n > 0 && result == 1)
{
if ((n & 1) == back)
{
// When two consecutive bits are same
result = 0;
}
else
{
back = n & 1;
}
n = n >> 1;
}
// Display given number
print("\n Number : " + num);
if (result == 0)
{
print("\n No");
}
else
{
print("\n Yes");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Sequence = new Sequence();
var num: Int = 85;
// 85 (1010101)
num = 42;
// 42 (101010)
num = 106;
// 106 (1101010)
num = 2;
// 2 (10)
num = 22;
// 22 (10110)
}
}``````

#### Output

`````` Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No``````
``````/*
Swift 4 program
Check if a number has bits in alternate pattern
*/
class Sequence
{
// Check that bit pair are different in given number or not
func alternatePattern(_ num: Int)
{
if (num <= 0)
{
return;
}
// Get given number
var n: Int = num;
// Result indicator
var result: Int = 1;
// Get last bit
var back: Int = n & 1;
// left shift by one
n = n >> 1;
// Execute loop until
while (n > 0 && result == 1)
{
if ((n & 1) == back)
{
// When two consecutive bits are same
result = 0;
}
else
{
back = n & 1;
}
n = n >> 1;
}
// Display given number
print("\n Number : ", num, terminator: "");
if (result == 0)
{
print("\n No", terminator: "");
}
else
{
print("\n Yes", terminator: "");
}
}
}
func main()
{
var num: Int = 85;
// 85 (1010101)
num = 42;
// 42 (101010)
num = 106;
// 106 (1101010)
num = 2;
// 2 (10)
num = 22;
// 22 (10110)
}
main();``````

#### Output

`````` Number :  85
Yes
Number :  42
Yes
Number :  106
No
Number :  2
Yes
Number :  22
No``````
``````/*
Kotlin program
Check if a number has bits in alternate pattern
*/
class Sequence
{
// Check that bit pair are different in given number or not
fun alternatePattern(num: Int): Unit
{
if (num <= 0)
{
return;
}
// Get given number
var n: Int = num;
// Result indicator
var result: Int = 1;
// Get last bit
var back: Int = n and 1;
// left shift by one
n = n shr 1;
// Execute loop until
while (n > 0 && result == 1)
{
if ((n and 1) == back)
{
// When two consecutive bits are same
result = 0;
}
else
{
back = n and 1;
}
n = n shr 1;
}
// Display given number
print("\n Number : " + num);
if (result == 0)
{
print("\n No");
}
else
{
print("\n Yes");
}
}
}
fun main(args: Array < String > ): Unit
{
var num: Int = 85;
// 85 (1010101)
num = 42;
// 42 (101010)
num = 106;
// 106 (1101010)
num = 2;
// 2 (10)
num = 22;
// 22 (10110)
}``````

#### Output

`````` Number : 85
Yes
Number : 42
Yes
Number : 106
No
Number : 2
Yes
Number : 22
No``````

Resultant Output Explanation:

Let's analyze the output for the provided examples:

1. Number: 85 (1010101) The binary representation of 85 has alternating bits (1010101), and the function correctly outputs "Yes."

2. Number: 42 (101010) The binary representation of 42 has alternating bits (101010), and the function correctly outputs "Yes."

3. Number: 106 (1101010) The binary representation of 106 does not have alternating bits (1101010), as the first two bits are the same (11). The function correctly outputs "No."

4. Number: 2 (10) The binary representation of 2 has alternating bits (10), and the function correctly outputs "Yes."

5. Number: 22 (10110) The binary representation of 22 does not have alternating bits (10110), as the first two bits are the same (10). The function correctly outputs "No."

Time Complexity:

The time complexity of the provided algorithm is O(log n), where n is the given input number. This is because the algorithm performs a right shift operation (`n = n >> 1`) in each iteration of the while loop, reducing the number `n` by half until it becomes 0. Since the number of bits in the binary representation of `n` is proportional to log n, the overall 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