如何在不使用任何算術運算的情況下找到x mod 15？

給出一個無符號整數，假設。並且不使用任何算術運算符，即+-/*或%，我們將找到x mod 15。我們可能會使用二進制位操作。如何在不使用任何算術運算的情況下找到x mod 15？

據我所知，我以2分爲基礎得出了這個結論。

a = a mod 15 = a mod 16爲a<15

讓a = x mod 15 然後a = x - 15k（對於一些非負k）。

即a = x - 16k + k ...

即a mod 16 = (x mod 16 + k mod 16) mod 16

即a mod 15 = (x mod 16 + k mod 16) mod 16

即a = (x mod 16 + k mod 16) mod 16

確定。現在來實現這一點。 A mod16的操作基本上是& OxF。和k基本上是x>>4

因此a = (x & OxF + (x>>4) & OxF) & OxF。

歸結爲添加2個4位數字。這可以通過位表達式來完成。

sum[0] = a[0]^b[0]

sum[1] = a[1]^b[1]^(a[0] & b[0])

... 等

這似乎是騙我的。我希望有一個更優雅的解決方案

來源

2011-07-12 shreedhar

我沒有看到任何錯誤，沒有使用算術運算符，而是隻使用按位運算符，它可能是他們想要的。 –

作業嗎？如果是 - 它應該被標記。 – bezmax

不做功課。有朋友向我提出這個問題的挑戰。 – shreedhar

這讓我想起了一個來自10號被稱爲「趕出9s」的舊技巧。這用於檢查手工執行的大量和的結果。在這種情況下123 mod 9 = 1 + 2 + 3 mod 9 = 6。

發生這種情況是因爲9小於數字（10）的基數。（省略證明））

所以考慮基數16（十六進制）中的數字。你應該可以這樣做：

0xABCE123 mod 0xF = (0xA + 0xB + 0xC + 0xD + 0xE + 0x1 + 0x2 + 0x3) mod 0xF 
        = 0x42 mod 0xF 
        = 0x6

現在你仍然需要做一些魔法才能使添加消失。但它給出了正確的答案。

UPDATE：

繼承人在C++完整實現。 f查找表將數字對與它們的和模15（其與字節模15相同）進行比較。然後，我們重新包裝這些結果，並且每輪重複應用一半的數據。

#include <iostream> 

uint8_t f[256]={ 
    0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,0, 
    1,2,3,4,5,6,7,8,9,10,11,12,13,14,0,1, 
    2,3,4,5,6,7,8,9,10,11,12,13,14,0,1,2, 
    3,4,5,6,7,8,9,10,11,12,13,14,0,1,2,3, 
    4,5,6,7,8,9,10,11,12,13,14,0,1,2,3,4, 
    5,6,7,8,9,10,11,12,13,14,0,1,2,3,4,5, 
    6,7,8,9,10,11,12,13,14,0,1,2,3,4,5,6, 
    7,8,9,10,11,12,13,14,0,1,2,3,4,5,6,7, 
    8,9,10,11,12,13,14,0,1,2,3,4,5,6,7,8, 
    9,10,11,12,13,14,0,1,2,3,4,5,6,7,8,9, 
    10,11,12,13,14,0,1,2,3,4,5,6,7,8,9,10, 
    11,12,13,14,0,1,2,3,4,5,6,7,8,9,10,11, 
    12,13,14,0,1,2,3,4,5,6,7,8,9,10,11,12, 
    13,14,0,1,2,3,4,5,6,7,8,9,10,11,12,13, 
    14,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14, 
    0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,0}; 

uint64_t mod15(uint64_t in_v) 
{ 
    uint8_t * in = (uint8_t*)&in_v; 
    // 12 34 56 78 12 34 56 78 => aa bb cc dd 
    in[0] = f[in[0]] | (f[in[1]]<<4); 
    in[1] = f[in[2]] | (f[in[3]]<<4); 
    in[2] = f[in[4]] | (f[in[5]]<<4); 
    in[3] = f[in[6]] | (f[in[7]]<<4); 

    // aa bb cc dd => AA BB 
    in[0] = f[in[0]] | (f[in[1]]<<4); 
    in[1] = f[in[2]] | (f[in[3]]<<4); 

    // AA BB => DD 
    in[0] = f[in[0]] | (f[in[1]]<<4); 

    // DD => D 
    return f[in[0]]; 
} 


int main() 
{ 
    uint64_t x = 12313231; 
    std::cout<< mod15(x)<<" "<< (x%15)<<std::endl; 
}

來源

2011-07-12 09:21:55

爲了避免增加，你可以使用一個16x16的查找表。 :-) – ShreevatsaR

@ShreevatsaR - 確實算法看起來很詭異，但可以減少到不太多的操作。所以我已經添加了它的實現... –

（頭部爆炸）好主意無論如何：D – bezmax

你的邏輯是有點缺陷，但我不能把它放在手指上。你自己想一想，你的最終公式在前8位運行，而忽略其餘部分。這隻有在你丟棄的部分（9+位）是總是乘以15時纔有效。然而，實際上（在二進制數中）9+位通常是16而不是15的乘法。例如，嘗試把1 0000 0000和11 0000 0000在你的公式中。你的公式會給出兩種情況的結果，而實際上答案是1和3.

在本質上，我幾乎可以肯定，你的任務不能沒有循環解決。如果您可以使用循環 - 那麼實現bitwiseAdd函數並做任何您喜歡的操作都不會輕鬆。

補充：

找到你的問題。它是：

... a = x - 15k（對於某些非負k）。

...並且k基本上是x >> 4

它等於x >> 4僅對於某些數字的純巧合。舉一個大的例子，例如x = 11110000。通過你的計算k = 15，而實際上它是k = 16：16 * 15 = 11110000.

來源

2011-07-12 08:45:41 bezmax

具體而言，當且僅當寫入x = 15k + r（其中0≤r<15）時，k是x >> 4當且僅當floor（x/15）= floor（x/16）時，我們有16k ≤X<16（K + 1）。這又意味着k≤r ShreevatsaR

如何在不使用任何算術運算的情況下找到x mod 15？

回答

相關問題