如何快速评估零集？

Question

这个最近的代码高尔夫职位询问了C中快速实现的可能性(假设n是无符号整数):

if (n==6 || n==8 || n==10 || n==12 || n==14 || n==16 || n==18 || n==20)

一种可能的简化是观察数字a[]={6,8,10,12,14,16,18,20}形成算术级数,因此改变范围然后使用一些按位技巧

if (((n - 6) & 14) + 6 == n)

正如John Bollinger 所回答的那样,实现了更短(可能确实更有效)的实现.

现在我问的是什么是类似优雅(并且希望同样有效)的实现

if (n==3 || n==5 || n==11 || n==29 || n==83 || n==245 || n==731 || n==2189)

提示:这次数字a[k]形成几何级数:a[k]=2+3^k.

我想在一般情况下,不能比排序数字更好a[k],然后进行对数搜索以测试是否n是排序数组的成员.

Answer 1

if ((n > 2) && (2187 % (n - 2) == 0))

检查(n - 2)功率3是否小于或等于2187(3的幂为7)

作为概括,要检查是否有任何无符号整数n是素数的幂k,您可以检查是否n除以k可以存储在无符号整数中的最大幂.

Answer 2

这非常类似于识别三个幂,您可以适应这种解决方案:

bool test(unsigned x) {
    x -= 2;
    if (x > 2187)
        return 0;
    if (x > 243)
        x *= 0xd2b3183b;
    return x <= 243 && ((x * 0x71c5) & 0x5145) == 0x5145;
}

在给定的范围内,这可以进一步简化(通过蛮力找到):

bool test2(unsigned x) {
  x -= 2;
  return x <= 2187 && (((x * 0x4be55) & 0xd2514105) == 5);
}

Answer 3

提示:这次数字a[k]形成几何级数:a[k]=2+3^k.

n = 2 + 3^k
n - 2 = 3^k

(n - 2) / 3^k = 1
(n - 2) % 3^k = 0

k = 0 ~ n-2 = 3^0 = 1, n = 3
k = 1 ~ n-2 = 3^1 = 3, n = 5
k = 2 ~ n-2 = 3^3 = 9, n = 11

if (n > 2 && isPow(n-2, 3))

与功能的定义 isPow(x,y)

bool isPow(unsigned long x, unsigned int y)
{
    while (x % y == 0)
    {
        x /= y;
    }

    return x == 1;
}

n = n  ~ n-2 = 3^k/3 = 3^(k-1)/3 = .. = 3^1/3 = 1%3 != 0
n = 11 ~ n-2 = 9/3 = 3/3 = 1%3 != 0
n = 5  ~ n-2 = 3/3 = 1%3 != 0
n = 3  ~ n-2 = 1%3 != 0

同样我们可以扣除k..

int k = findK(n-2, 3);

int findK(unsigned long x, unsigned int y)
{
    unsigned int k = 0;

    while (x % y == 0)
    {
        x /= y;
        k++;
    }

    if (x == 1) return k;
    else return (-1);
}

n - 2 = 3 * 3^(k-1)       for k > 0
(n - 2) / 3 = 3^(k-1)
(n - 2) / 3 / 3 = 3^(k-2)
(n - 2) / 3 / 3 / 3 = 3^(k-3)
(n - 2) / 3 / 3 / 3 / 3 = 3^(k-4)
..
(n - 2) / 3 / 3 / ..i times = 3^(k-i)
..
(n - 2) / 3 / 3 / ..k times = 3^0 = 1