程序检查给定的整数是否具有替代模式

Question

我对C非常陌生,尤其是位操作程序.我正在练习一些并遇到一个问题 - "C程序来检查给定的整数是否具有替代模式".以下是解决方案,我无法准确理解这段代码的作用和问题.替代模式意味着什么？

#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 1

"交替模式"表示其中没有两个相邻比特相同的模式,即类似01010101或的模式10101010.

解决方案有两个部分:

• 第一部分将一个数字与自身组合在一起
• 第二部分验证结果是2 ⁿ -1

第一部分使用XOR运算符^,1仅当两个进行异或运算的位不同时才生成.由于我们正在对一个自身向右移动的数字进行异或,因此交替模式会生成所有数字; 任何其他模式都会在中间产生至少一个零.

第二部分在XOR的结果中加一,并通过重复除以二来检查结果为2 ⁿ.这不是最有效的方法,但更好的替代方案是不那么直观:你可以验证自身减去1的编号是零:

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

演示.

注意:在32位系统上,此解决方案适用于最多31位的数字.如果使用了signed type num,则该值必须为非负值.