CODEWITHSUNDEEP
cbit-manipulation
Ravi
Ravi

Reputation: 79

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");
    }
}

Upvotes: 1

Views: 4968

Answers (3)

harsh biyani
harsh biyani

Reputation: 31

Try this method:

public static boolean isAlternatePattern(int num) {
        int mask1 = 0X55555555;
        int mask2 = 0XAAAAAAAA;
        return (num & mask1) == num || (num & mask2) == num;
}

Upvotes: 2

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726509

"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 right 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 right, 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");

Demo.

Note: On 32-bit systems this solution works for numbers with up to 31 bits. If signed type is used for num, the value must be non-negative.

Upvotes: 8

Nazeem
Nazeem

Reputation: 59

Code works fine for numbers with alternate pattern having lsb as 1(010101). But if lsb is 0(As in 10101010), code doesn't works good. In this case, either right shift is preferred or additional increment is required to produce all ones.`

    void main()
    {
        int num, x, y;
        printf("enter the number:");
        scanf("%d", &num);
        x = num << 1;
        y = x ^ num;
        y = y + 1;
        if (!(num&1))//Additional increment if lsb is 0 to get all 1's
            y++;

        if (y && (!(y&y-1)))//checking power of 2
            printf("\n%d has an alternate pattern\n",num);
        else
            printf("\n%d has no alternate pattern\n",num);

    }

`

Upvotes: 1

Related Questions