c - 我怎么知道一个数字是否可以从1开始递增4？

Question

我需要知道一个数字是否可以通过迭代递增 1 乘以 4 来获得。这些数字是 5、9、13、17、21 等。为此，我目前正在执行以下操作:

#include <stdio.h>

int main() {
  int number = 13;
  int i;
  for (i = n; i > 0; i -= 4) {
    if (i == 1) {
      printf("yes\n");
      break;
    }
  }
  if (i <= 0)
    printf("no\n");
}

但这似乎是一种极其低效的 O(n) 方法。我很感激 O(1) 解决方案，我可以做得更好吗？

Answer 1

显然，您要检查数字 n 是否具有以下形式

n = 1+4k

所以你只需要检查它的前身是否能被 4 整除。

如果你有二进制 2 的补码，如果最后 2 位为 0，则属于后者。

因此:

int check(int n) { return (n-1)&3 == 0; }

为了让帽子更短，1+4k 形式的数字的最后两位为 s01:

    int check(int n) { return n&3 == 1; }