Ravi Ravi - 4 months ago 35
C Question

Program to Check whether the given Integer has an Alternate Pattern

I am very much new to C, and particularly the bit manipulation programs.
I was practicing a few and came across a problem termed- "C Program to Check whether the given Integer has an Alternate Pattern". The following is the solution ,I couldn't understand exactly what this code does and the question.What does alternate pattern mean?

#include <stdio.h>

void main()
{
int num, x, y, count = 0;

printf("enter the number:");
scanf("%d", &num);
x = num << 1;
y = x ^ num;
y = y + 1;


while ((y / 2) != 0)
{
if (y % 2 != 0)
{
count++;
break;
}
else
{
y = y / 2;
}
}
if (count)
{
printf("false");
}
else
{
printf("true");
}
}

Answer

"Alternating pattern" means a pattern in which no two adjacent bits are the same, i.e. a pattern like 01010101 or 10101010.

The solution has two parts:

  • Part one combines a number with itself shifted left by one bit
  • Part two verifies that the result is 2n-1

Part one uses XOR operator ^, which produces a 1 only when the two bits being XOR-ed are different. Since we are XOR-ing a number with itself shifted left, an alternating pattern would produce all ones; any other pattern would produce at least one zero in the middle.

Part two adds one to the result of the XOR, and checks that the result is 2n by repeated division by two. This is not the most efficient way of doing it, but a better alternative is a lot less intuitive: you can verify that the number AND-ed with itself minus one is zero:

printf("enter the number:");
scanf("%d", &num);
x = num << 1;
y = x ^ num;
printf("%s\n", y & (y+1) ? "false" : "true");