有沒有什麼辦法可以在沒有模/數運算符的情況下編寫「mod 31」？

Question

如果您的操作數是2的冪，則可以在沒有模數運算符或除法的情況下輕鬆獲取數字的模數。在這種情況下，以下公式成立：x % y = (x & (y − 1))。在許多體系結構中，這通常具有很高的性能。對於mod 31可以做同樣的事嗎？

int mod31(int a){ return a % 31; }; 

Answer 1

您可以使用連續的加/減法。沒有其他的技巧，因爲31是一個素數，看看N的模數是多少，你將不得不除以餘數。

int mode(int number, int modulus) { 
    int result = number; 

    if (number >= 0) { 
     while(result > modulus) { result = result - modulus;} 
    } else { 
     while (result < 0) { result = result + modulus;) 
    } 
} 

Answer 2

int mod31(int a){ 
    while(a >= 31) { 
     a -= 31; 
    } 
    return a; 
}; 

它的工作原理，如果a > 0，但我懷疑這將是快於%運營商。

Answer 3

以下是解決此問題的兩種方法。第一個使用普通的比特旋轉技術，如果仔細優化可以擊敗硬件部門。另一個用一個乘法代替除法，類似於gcc執行的優化，並且是最快的。最重要的是，如果第二個參數是常量，因爲gcc被覆蓋了，所以沒有太大的意圖試圖避免%運算符。 （可能還有其他編譯器。）

以下函數基於x與x的基數爲32的數字之和相同（mod 31）的事實。這是事實，因爲32是1 mod 31，因此32的任何功率是1 mod 31。因此，基數爲32的數字中的每個「數字」位置將數字* 1貢獻給模31總和。獲得基數爲32的表示很容易：我們一次只取5位。 （與此答案中的其餘功能一樣，它只適用於非負數的x）。

unsigned mod31(unsigned x) { 
    unsigned tmp; 
    for (tmp = 0; x; x >>= 5) { 
    tmp += x & 31; 
    } 
    // Here we assume that there are at most 160 bits in x 
    tmp = (tmp >> 5) + (tmp & 31); 
    return tmp >= 31 ? tmp - 31 : tmp; 
} 

對於一個特定的整數大小，你可以展開循環，很可能擊敗分裂。使用無符號（而看到@chux's answer一種方式來循環轉換成O(log bits)操作，而不是O(bits)它更難以被擊敗gcc，避免了分裂;如果被除數是在編譯時已知常數。

在一個非常快的標杆32位整數，這個天真的展開循環花了19秒，基於@ chux的回答只有13秒，但gcc的x%31花費了9.7秒。強制gcc使用硬件劃分（通過使劃分非常量）耗時23.4秒，上面顯示的代碼需要25.6秒，這些數字應該用幾粒鹽來計算，時間是計算i%31的所有可能值i，在我的筆記本電腦上使用-O3 -march=native

gcc通過用常數的倒數和右移代替實際上是64位乘法來避免32位除法。 （實際的算法做了更多的工作以避免溢出。）該程序在20多年前在gcc v2.6中實現，描述該算法的論文可在gmp site上獲得。 （GMP也使用這個技巧。）

這裏是一個簡化版本：假設我們想要計算一些無符號的32位整數（使用pythonic //來指示截斷整數除法）n // 31。我們使用「魔術常數」m = 232 // 31，這是138547332。現在，很顯然，對於任何n：

m * n <= 232 * n/31 < m * n + n ⇒ m * n // 232 <= n//31 <= (m * n + n) // 232

（在這裏我們使用的事實，如果a < b然後floor(a) <= floor(b)。）

此外，由於n < 232，m * n // 232和(m * n + n) // 232是相同的整數或兩個連續的整數。因此，這兩個中的一個（或兩個）是n//31的實際值。

現在，我們真的想要計算n%31。所以我們需要將（推測）商乘以31，並從n中減去該商。如果我們使用了兩種可能的商中較小的，它可能是，計算出的模值過大，但它只能是由31

太大或者，把它放在代碼：

static unsigned long long magic = 138547332; 
unsigned mod31g(unsigned x) { 
    unsigned q = (x * magic) >> 32; 
    // To multiply by 31, we multiply by 32 and subtract 
    unsigned mod = x - ((q << 5) - q); 
    return mod < 31 ? mod : mod - 31; 
} 

海灣合作委員會使用的實際算法通過使用基於乘以237//31 + 1的稍微更精確的計算來避免最後的測試。這總是產生正確的商，但是以一些額外的移位爲代價，並且爲避免整數溢出而添加。事實證明，上述版本稍微快一點 - 在與上述相同的基準測試中，僅需要6.3秒。

---

其他基準比較的功能，完整性：

天真展開循環

unsigned mod31b(unsigned x) { 
    unsigned tmp = x & 31; x >>= 5; 
    tmp += x & 31; x >>= 5; 
    tmp += x & 31; x >>= 5; 
    tmp += x & 31; x >>= 5; 
    tmp += x & 31; x >>= 5; 
    tmp += x & 31; x >>= 5; 
    tmp += x & 31; 

    tmp = (tmp >> 5) + (tmp & 31); 
    return tmp >= 31 ? tmp - 31 : tmp; 
} 

@ chux的改善，略微優化

static const unsigned mask1 = (31U << 0) | (31U << 10) | (31U << 20) | (31U << 30); 
static const unsigned mask2 = (31U << 5) | (31U << 15) | (31U << 25); 
unsigned mod31c(unsigned x) { 
    x = (x & mask1) + ((x & mask2) >> 5); 
    x += x >> 20; 
    x += x >> 10; 

    x = (x & 31) + ((x >> 5) & 31); 
    return x >= 31 ? x - 31: x; 
} 

Answer 4

如果你想得到分母的模數d這樣d = (1 << e) - 1其中e是一些指數，你可以使用這樣一個事實，即二進制擴展的1/d是一個重複部分，每個e位都設置一個位。例如，對於e = 5,d = 31和1/d = 0.0000100001...。

類似rici’s answer，該算法有效計算的a的鹼基(1 << e)數字的總和：

uint16_t mod31(uint16_t a) { 
    uint16_t b; 
    for (b = a; a > 31; a = b) 
     for (b = 0; a != 0; a >>= 5) 
      b += a & 31; 
    return b == 31 ? 0 : b; 
} 

您可以展開這個循環中，因爲分母位的分子數量都不變，但讓編譯器這樣做可能會更好。當然，您可以將5更改爲輸入參數，將31更改爲由此計算出的變量。

Answer 5

[EDIT2]下面對性能注意到

試圖只用1 if條件。

這種方法是O（log2（sizeof unsigned））。如果代碼使用uint64_t，那麼運行時間將增加1組和和/加/加，而不是兩倍的時間。

unsigned mod31(uint32_t x) { 
    #define m31 (31lu) 
    #define m3131 ((m31 << 5) | m31) 
    #define m31313131 ((m3131 << 10) | m3131) 

    static const uint32_t mask1 = (m31 << 0) | (m31 << 10) | (m31 << 20) | (m31 << 30); 
    static const uint32_t mask2 = (m31 << 5) | (m31 << 15) | (m31 << 25); 
    uint32_t a = x & mask1; 
    uint32_t b = x & mask2; 
    x = a + (b >> 5); 
    // x = xx 0000x xxxxx 0000x xxxxx 0000x xxxxx 

    a = x & m31313131; 
    b = x & (m31313131 << 20); 
    x = a + (b >> 20); 
    // x = 00 00000 00000 000xx xxxxx 000xx xxxxx 

    a = x & m3131; 
    b = x & (m3131 << 10); 
    x = a + (b >> 10); 
    // x = 00 00000 00000 00000 00000 00xxx xxxxx 

    a = x & m31; 
    b = x & (m31 << 5); 
    x = a + (b >> 5); 
    // x = 00 00000 00000 00000 00000 0000x xxxxx 

    return x >= 31 ? x-31 : x; 
} 

[編輯]

第一加法方法總結個體7組5位的並行。隨後的添加將7組分成4個，然後是2，然後是1.然後，這個最終的7位和繼續將其上半部分（2位）添加到其下半部分（5位）。然後代碼使用一個測試來執行最終的「mod」。

此方法適用於範圍更廣的unsigned至多uint165_t log2（31 + 1）*（31 + 2）。通過這個，需要更多的代碼。

請參閱@rici進行一些優化。仍然推薦使用uint32_t與unsigned和31UL，如31U << 15那樣轉換，因爲unsigned 31U可能只有16位長。 （2014年在嵌入式世界中流行的16位int）。

---

[EDIT2]

除了讓編譯器使用其優化器，2個額外的技術加速性能。這些都是較小的客廳技巧，取得了適度的改進。請記住YMMV，這是32位的unsigned。

使用表查找最後的modulo提高了10-20％。使用unsigned t表而不是unsigned char t也有所幫助。事實證明，表格長度，因爲第一次預期需要2 * 31，只需要31 + 5。

使用局部變量而不是始終調用函數參數出人意料地有所幫助。可能在我的gcc編譯器中有一個弱點。

發現非分支解決方案，未顯示，以取代x >= 31 ? x-31 : x。但是他們的編碼複雜度更高，性能更慢。

總而言之，一個有趣的練習。

unsigned mod31quik(unsigned xx) { 
    #define mask (31u | (31u << 10) | (31u << 20) | (31u << 30)) 
    unsigned x = (xx & mask) + ((xx >> 5) & mask); 
    x += x >> 20; 
    x += x >> 10; 
    x = (x & 31u) + ((x >> 5) & 31u); 

    static const unsigned char t[31 * 2 /* 36 */] = { 0, 1, 2, 3, 4, 5, 6, 
     7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 
     25, 26, 27, 28, 29, 30, 0, 1, 2, 3, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; 
    return t[x]; 
}