Program to Check whether the given Integer has an Alternate Pattern

Question

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

Wherever you found example this should explain what an "alternate pattern" means. — dbush, Aug 01 '16 at 02:41
@dbush Apparently, [it does no such thing](http://www.sanfoundry.com/c-program-integer-alternate-pattern/). I'm assuming that's where the OP ripped this off from. — WhozCraig, Aug 01 '16 at 02:49

score 8 · Accepted Answer · edited Nov 19 '17 at 00:14

8

"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 2ⁿ-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 2ⁿ 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.

edited Nov 19 '17 at 00:14

sonorous

71
6

answered Aug 01 '16 at 02:50

Sergey Kalinichenko

714,442
84
1,110
1,523

Your code seems wrong. For example for 2, 10, 42 and 170 you print `false` even though their bit patterns are `10`, `1010`, `101010` and `10101010`. Do I misunderstand something? – Stefan Pochmann Oct 06 '17 at 15:00
@StefanPochmann You are right, I was assuming odd numbers; the solution did not work for even numbers. The fix was straightforward the code needs to shift odd and even numbers in different directions. Please see the edit. – Sergey Kalinichenko Oct 06 '17 at 15:27
Hmm, actually I think you can just *always* shift *right*, no? – Stefan Pochmann Oct 06 '17 at 18:19
@StefanPochmann Thank you very much for a very good observation! I updated the answer and the demo. – Sergey Kalinichenko Oct 06 '17 at 18:25

score 1 · Answer 2 · answered Oct 01 '16 at 19:51

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

    }

`

score 1 · Answer 3 · edited Jan 01 '20 at 07:19

1

Try this method:

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

edited Jan 01 '20 at 07:19

Ṃųỻịgǻňạcểơửṩ

2,517
8
22
33

answered Jan 01 '20 at 06:14

harsh biyani

21
7

Program to Check whether the given Integer has an Alternate Pattern

3 Answers3