algorithm - 使用 1 位变量确定数字是否为数字回文

Question

我在一个显示谷歌面试问题的网站上看到了这个问题。

我不知道如何解决这个问题。

如果我们允许保留一些其他变量，那么我建议保留 2 个索引，1 个指向开头，另一个指向结尾。然后使用 bit 变量比较它们中的 2 个（通过位操作）。

但是如果我们不允许使用更多的变量，我不知道如何解决它。

Answer 1

为了使 2n 位的数目成为回文，位置 i 处的每个位必须等于索引 (2n-i) 处的位。使用异或 (XOR) 单个位可以很容易地进行比较：当且仅当位 a 和 b 不相等时，a XOR b == 1。因此，当以这种方式比较每一对相应的位（见上文）并通过对所有单位比较结果进行 OR 运算来构建结果时，回文数将为 0，任何其他数字为 1。

Answer 2

我假设我们在谈论按位回文（即 3 = 11 是，但 2 = 10 不是）。

我看到有两种可能性：

（我已经为每个编写了一些 Java 代码。一些括号只是为了便于阅读而包括在内）

• 指数不算作变量。

  我要说的第一件事可能是“但索引是变量......”。

  一旦我们得到不匹配，我们就可以循环这个数字并返回。

  digits下面是一个变量，但只是为了便于阅读——它可以很容易地替换到 if 语句中。

  的公式digits是在一些玩弄之后出现的（可能有一个更简单的方法）。

  boolean isPalidrome(int number)
  {
     int digits = (int)Math.ceil(Math.ceil(Math.log10(1+number)/Math.log10(2)))-1;
     for (int i = 0; number/2 >> i != 0; i++)
     {
        if (((number >> i) & 1) != (((number >> digits - i) & 1)))
           return false;
     }
     return true;
  }
  

• 指数确实算作变量。

  这可以通过基本上展开上述循环来完成，假设我们得到一个固定大小的数字（例如int32 位）。

  我将类型更改为，byte因为我并没有真正看到本质上复制那么多行的意义。byte只有 8 位，所以我们只需要 4 次检查，带有中断条件。

  再次digits是一个变量，但不需要是。

  boolean isPalidrome(byte number)
  {
     int digits = (int)Math.ceil(Math.ceil(Math.log10(1+number)/Math.log10(2)))-1;
     if ((number & 1) != (((number >> digits) & 1)))
        return false;
     if ((number/2 >> 1) == 0)
        return true;
     if (((number >> 1) & 1) != (((number >> (digits - 1)) & 1)))
        return false;
     if ((number/2 >> 2) == 0)
        return true;
     if (((number >> 2) & 1) != (((number >> (digits - 2)) & 1)))
        return false;
     if ((number/2 >> 3) == 0)
        return true;
     if (((number >> 3) & 1) != (((number >> (digits - 3)) & 1)))
        return false;
     return true;
  }
  

  如果需要，上述内容也可以包含在单个语句中。

  如果我们被允许修改实际数字，也可以像上面那样检查第一位和最后一位，但是然后修改数字以去除第一位和最后一位，所以我们可以只检查第一位和最后一位，直到数字为零。

现场演示。

请注意，以上都没有使用位变量。也许位变量只是为了作为一个标志来跟踪数字是否是回文。