如何检查一个数字是否为“位回文数”

Question

我需要编写一个程序来检查数字是否为位回文数。例如，数字9（二进制下为1001）是位回文数，而6（110）不是位回文数。

我已经编写了将数字转换为二进制字符串并检查其是否为回文字符串的代码。有更好的方法吗？

- user2797512

Answer 1

我们可以使用位运算符来实现。其思想是从右到左逐位读取数字的每一位，并使用这些位从左到右生成另一个数字。最后，我们比较这两个数字。如果它们相同，则原始数字是二进制回文数。

int isBitPalindrome(int x) {
    int reversed = 0, aux = x;
    while (aux > 0) {
        /* 
        Before doing that shifting reversed to 
        right, to build it from left to right. 
        Takes LSB of aux and puts it as LSB of reversed
        variable.
        */
        reversed = (reversed  << 1) | (aux & 1);

        /*
        Loop depends on number of bits in aux. Takes next bit into 
        LSB position by shifting aux right once.
        */
        aux = aux >> 1;
    }
    return (reversed  == x) ? 1 : 0;
}

- Vallabh Patade

---

方法听起来不错，但代码可读性很差。为什么变量名没有意义呢？好的变量名应该是 x、reversed 和 remain。为什么返回值需要进行逻辑与整型转换？请尝试编写接近可读英语的代码，并使用注释来解释更复杂的部分（比如构建“y”）。 - Thomas W

@ThomasW 感谢您的建议。我已经在我的代码中进行了更改。 - Vallabh Patade

太好了！逻辑处理得很好。 - Thomas W

Answer 2

以下实现将在O(n/2)的时间复杂度内执行，其中n是给定数字的位数：

#define LSB(bit_len) 0x1
#define MSB(bit_len) 0x1 << bit_len - 1

int isBitPalindrome(int x) {
    int i = 0, bit_len = sizeof(int) * 8;
    unsigned int left = 0, right = 0;

    while (i < bit_len / 2) {
        left = x << i & MSB(bit_len);
        right = x >> i & LSB(bit_len);

        if ((left == 0x0 && right == 0x0) ||
            (left == MSB(bit_len) && right == LSB(bit_len))
            i++;
        else
            break;
    }

    return (i == bit_len / 2) ? 1 : 0;
}

- Ganapathi Bhat