如何检查整数的二进制表示是否为回文？

Question

如何检查整数的二进制表示是否为回文？

- yesraaj

---

10001是回文数吗？或者必须是完整的字节-00100100？还是必须是完整的整数-00000000 00000001 10000000 00000000？ - jmucchiello

“0110”不是回文，因为它实际上是“110”，对吗？这意味着所有非零回文数都是奇数。 - Keith Thompson

Answer 1

希望是正确的：

_Bool is_palindrome(unsigned n)
{
    unsigned m = 0;

    for(unsigned tmp = n; tmp; tmp >>= 1)
        m = (m << 1) | (tmp & 1);

    return m == n;
}

- Christoph

Answer 2

由于您没有指定要使用哪种语言，这里提供一些C代码（虽然不是最有效的实现方式，但它可以说明问题）：

/* flip n */
unsigned int flip(unsigned int n)
{
    int i, newInt = 0;
    for (i=0; i<WORDSIZE; ++i)
    {
        newInt += (n & 0x0001);
        newInt <<= 1;
        n >>= 1;
    }
    return newInt;
}

bool isPalindrome(int n)
{
    int flipped = flip(n);
    /* shift to remove trailing zeroes */
    while (!(flipped & 0x0001))
        flipped >>= 1;
    return n == flipped;
}

编辑已经针对你的10001个问题进行修复。

- rlbond

---

我喜欢这个解决方案，因为它非常简单。在代码和算法上都非常清晰明了。 - Kevin Anderson

整数（或您想要使用的任何数据类型）中的位数。 - colithium

此代码在 isPalindrome(0x0) 中进入了一个无限循环。我认为它存在一个 off by 1 错误，即将 newInt 向左移动了一个过多。 - colithium

Answer 3

创建一个包含字符及其位反转字符的256行图表。给定一个4字节整数，取第一个字符，在图表中查找并将答案与整数的最后一个字符进行比较。如果它们不同，则不是回文；如果它们相同，则重复操作中间字符。如果它们不同，则不是回文；否则就是回文。

- Liran Orevi

---

这不太适用于大规模 -- 你会使用一个20亿行的图表来表示32位整数吗？ - rlbond

你不需要 - 你只需要一次比较字节。 - Martin Beckett

当然，这不像他所澄清的那样工作。 - rlbond

这假设数字是对齐的。101是回文，但0000 0000 0000 0101不是。 - Emre Sahin

Answer 4

这里有很多好的解决方案。让我添加一个我认为非常易读，虽然不是最有效的：

/* Reverses the digits of num assuming the given base. */
uint64_t
reverse_base(uint64_t num, uint8_t base)
{
  uint64_t rev = num % base;

  for (; num /= base; rev = rev * base + num % base);

  return rev;
}

/* Tells whether num is palindrome in the given base. */
bool
is_palindrome_base(uint64_t num, uint8_t base)
{
  /* A palindrome is equal to its reverse. */
  return num == reverse_base(num, base);
}

/* Tells whether num is a binary palindrome. */ 
bool
is_palindrome_bin(uint64_t num) 
{
  /* A binary palindrome is a palindrome in base 2. */
  return is_palindrome_base(num, 2);
}

- Stephan202

Answer 5

以下内容适用于任何无符号类型。（有符号类型的位运算往往会带来问题。）

bool test_pal(unsigned n)
{
  unsigned t = 0;

  for(unsigned bit = 1; bit && bit <= n; bit <<= 1)
    t = (t << 1) | !!(n & bit);

  return t == n;
}

- Dingo

---

+1；我的答案使用相同的算法，但是它不是将掩码左移，而是将值n向右移动。 - Christoph

Answer 6

int palidrome (int num) 
{ 
  int rev = 0; 
  num = number; 
  while (num != 0)
  { 
    rev = (rev << 1) | (num & 1); num >> 1; 
  }

  if (rev = number) return 1; else return 0; 
}

- user3059007

---

请确保您正确格式化答案，以便它们易于阅读。所有代码应缩进4个空格。谢谢！ - mdewitt

Answer 7

我知道这个问题已经发布了2年，但是我有一个更好的解决方案，它不依赖于单词大小和其他因素。

int temp = 0;
int i = num;
while (1)
{ // let's say num is the number which has to be checked
    if (i & 0x1)
    {
        temp = temp + 1;
    }
    i = i >> 1;
    if (i) {
        temp = temp << 1;
    }   
    else   
    {
        break;
    }
}   

return temp == num;

- brut3f0rc3

Answer 8

Javascript 解决方案

function isPalindrome(num) {
  const binaryNum = num.toString(2);
  console.log(binaryNum)
  for(let i=0, j=binaryNum.length-1; i<=j; i++, j--) {
    if(binaryNum[i]!==binaryNum[j]) return false;
  }
  return true;
}

console.log(isPalindrome(0))

- Vinit Khandelwal

Answer 9

我经常使用针对字符串的回文函数，如果是回文则返回true，否则返回false，例如在Java中。我需要做的唯一事情就是像这样：

int number = 245;
String test = Integer.toString(number, 2);
if(isPalindrome(test)){
   ...
}

- rapfaria

---

你“总是有一个回文函数”？为什么？ - Hejazzman

也许你误解了我的意思。 我的意思是我有一个可以处理字符串的回文函数，我可以在任何地方使用它。想一次，永久使用。 - rapfaria

问题是isPalindrome()的实现方式，但是具体地，涉及到二进制表示。 - xanadont

字符串测试 = Integer.toString(number, 2); 这样，数字将以二进制表示。 实现非常简单。您循环到字符串的中间，并将当前位置的字符与相应位置（test.length - current position）上的字符进行比较。如果它们不同，则返回false。当循环结束时，返回true。=) - rapfaria

Raphael的回答非常清晰明了，他将问题从二进制转换为字符串，并解决字符串是否为回文的问题相当简单。唯一需要注意的是，这个问题带有c,c++标签。 - Javier

Answer 10

我认为最好的方法是从两端开始，向内逐步比较，即比较第一位和最后一位、第二位和倒数第二位等等，这将具有O(N/2)的时间复杂度，其中N是整数的大小。如果在任何时候你的对应位不相同，那么它就不是回文。

bool IsPalindrome(int n) {
    bool palindrome = true;
    size_t len = sizeof(n) * 8;
    for (int i = 0; i < len / 2; i++) {
        bool left_bit = !!(n & (1 << len - i - 1));
        bool right_bit = !!(n & (1 << i));
        if (left_bit != right_bit) {
            palindrome = false; 
            break;
        }
    }
    return palindrome;
}

- i_am_jorf

---

无法编译：bool right_bit = !!(n & (1 << i); 缺少一个右括号。如果有前导零，比如17，这样做不会出错吗？ - dirkgently

但是奇怪的是，我们几乎使用了相同的版本（包括命名）。事实上，我运行了你的代码来确定差异和编译器错误。 - dirkgently

修复了缺失的括号。我假设，由于原帖没有指定，整个 int 的位域必须是回文的，而不是忽略前导零。但是现在你提到了这一点，按照那种方式做可能是有意义的。 - i_am_jorf

sizeof(n); 给出的是字节大小，而你需要的是位大小。 - dirkgently