如何通过从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将最后两位用作01:

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