如何快速評估零點集？

Question

這最近code golfing post要求用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}形成arithmetic progression，所以移位的範圍內，然後用一些bitwise tricks

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

導致更短（並且可能實際上更高效）的實現，如John Bollinger的answered。

現在我問什麼是類似優雅（希望同樣有效）實現

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 b; 
if (n >= 3 && n <= 2189) 
{ 
    double d = std::log(n - 2)/std::log(3); // log₃(n - 2) 
    b = std::trunc(d) == d; // Checks to see if this is an integer 
    // If ‘b’ then ‘n == a[log₃(n - 2)]’ 
} 
else b = false; 

if (b) 
{ 
    // your code 
} 

由於數量n是小的整數，浮點不準確不應該是一個問題。

當然，它不會像整數運算一樣快，它不適合貼在表達式上，它可能比某種數組搜索更快，特別是如果你在哪裏增加最大值。

編輯我測試我的代碼（未啓用優化），平均（對於所有n小於或等於2189）我的版本了185.849納秒wheras的||版本了116.546納秒（運行我的程序產生多次類似的結果），所以這不是更快。 也出於一些離奇的原因，它設置b到false當n == 245，（它應該是真的）。

Answer 3

發現在一個相關的帖子有類似的問題： 您可以使用std::find

bool found = (std::find(my_var.begin(), my_var.end(), my_variable) != my_var.end()); 
// my_var is a list of elements. 

（請確保您有<算法>）。

對於這種東西，在99％的情況下，有一個圖書館可以爲你做這項工作。

Answer 4

提示：這次數字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 

Similiarly我們可以扣除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 

Answer 5

的一個非常有效的方式做到這樣的事情是與一組，尤其是unordered_set。作爲散列表，搜索是平均常數，最差的線性。它也比一系列條件更加優雅，並且規模良好。

只需插入要比較的值和count該值中的值。如果找到它，這是您的測試值之一。

std::unordered_set<int> values; 
values.insert(3); 
values.insert(5); 
values.insert(11); 
values.insert(29); 
values.insert(83); 
values.insert(245); 
values.insert(731); 
values.insert(2189); 

... 

if(values.count(input)) 
    std::cout << "Value is in set.\n"; 
else 
    std::cout << "Value is NOT in set.\n"; 

Answer 6

這非常類似於recognizing a power of three，並且可以例如this solution適應：

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); 
}