使用位移除10？

Question

是否有可能通過使用純位移，加法，減法和也許乘以10來除無符號整數？使用資源非常有限且分割緩慢的處理器。

Answer 1

這裏的編制小整型常量部門當微軟編譯器做什麼。假設一個32位機（代碼可相應調整）：

int32_t div10(int32_t dividend) 
{ 
    int64_t invDivisor = 0x1999999A; 
    return (int32_t) ((invDivisor * dividend) >> 32); 
} 

這是怎麼回事這裏要說的是，我們要按照1/10 * 2^32基本接近倍增，然後除去2^32。這種方法可以適應不同的除數和不同的位寬。

這對於ia32體系結構非常適用，因爲它的IMUL指令會將64位產品放入edx：eax中，並且edx值將成爲所需的值。即一個緩慢的乘法指令（假設股息是EAX和商通過在EAX返回）

div10 proc 
    mov edx,1999999Ah ; load 1/10 * 2^32 
    imul eax    ; edx:eax = dividend/10 * 2 ^32 
    mov eax,edx   ; eax = dividend/10 
    ret 
    endp 

即使一臺機器上，這將是比軟件更快地劃分。

Answer 2

除法是減法，所以是的。向右移1（除以2）。現在從結果中減去5，計算你減法的次數，直到值小於5.結果是你做的減法的次數。哦，劃分可能會更快。

如果分頻器中的邏輯尚未爲您完成這項工作，那麼採用正常分頻將右移再除以5的混合策略可能會使您獲得性能提升。

Answer 3

當然，你可以，如果你能承受一些精度上的損失。如果你知道你的輸入值的值範圍，你可以提出一個位移和一個精確的乘法。 一些例子，你可以如何劃分10，60，...像這樣的博客描述格式time the fastest way可能。

temp = (ms * 205) >> 11; // 205/2048 is nearly the same as /10 

你的， 阿洛伊斯·克勞斯

Answer 4

儘管到目前爲止給出的答案與實際問題相符，但它們與標題不匹配。所以這裏的解決方案深受Hacker's Delight的啓發，它確實只使用了位移。

unsigned divu10(unsigned n) { 
    unsigned q, r; 
    q = (n >> 1) + (n >> 2); 
    q = q + (q >> 4); 
    q = q + (q >> 8); 
    q = q + (q >> 16); 
    q = q >> 3; 
    r = n - (((q << 2) + q) << 1); 
    return q + (r > 9); 
} 

我認爲這是缺乏乘法指令的架構的最佳解決方案。

Answer 5

在一次只能移動一個地方的體系結構上，一系列明顯的比較兩個乘以10的權力可能比黑客的解決方案更好。假設一個16位的分紅：

uint16_t div10(uint16_t dividend) { 
    uint16_t quotient = 0; 
    #define div10_step(n) \ 
    do { if (dividend >= (n*10)) { quotient += n; dividend -= n*10; } } while (0) 
    div10_step(0x1000); 
    div10_step(0x0800); 
    div10_step(0x0400); 
    div10_step(0x0200); 
    div10_step(0x0100); 
    div10_step(0x0080); 
    div10_step(0x0040); 
    div10_step(0x0020); 
    div10_step(0x0010); 
    div10_step(0x0008); 
    div10_step(0x0004); 
    div10_step(0x0002); 
    div10_step(0x0001); 
    #undef div10_step 
    if (dividend >= 5) ++quotient; // round the result (optional) 
    return quotient; 
} 

Answer 6

考慮到庫巴奧伯的迴應，還有一個在同一脈絡。它使用迭代逼近的結果，但我不希望有任何令人驚訝的表現。

假設我們必須找到x其中x = v/10。

我們將使用逆操作v = x * 10，因爲它具有很好的屬性，當x = a + b，然後x * 10 = a * 10 + b * 10。

讓我們使用x作爲迄今爲止保持最佳結果近似值的變量。搜索結束後，x將保留結果。我們將x的每個位b從最高有效位設置爲較低有效位，逐個比較(x + b) * 10與v。如果其小於或等於v，則位b設置在x中。爲了測試下一個位，我們只需將b一個位置向右移（除以二）。

通過在其他變量中保存x * 10和b * 10，我們可以避免乘以10。

我們得到以下算法通過10

uin16_t x = 0, x10 = 0, b = 0x1000, b10 = 0xA000; 
while (b != 0) { 
    uint16_t t = x10 + b10; 
    if (t <= v) { 
     x10 = t; 
     x |= b; 
    } 
    b10 >>= 1; 
    b >>= 1; 
} 
// x = v/10 

編輯來劃分v：獲得庫巴奧伯的算法，避免了變量x10的需要，我們可以減去vb10和v10。在這種情況下x10不再需要。該算法變得

uin16_t x = 0, b = 0x1000, b10 = 0xA000; 
while (b != 0) { 
    if (b10 <= v) { 
     v -= b10; 
     x |= b; 
    } 
    b10 >>= 1; 
    b >>= 1; 
} 
// x = v/10 

環路可以unwinded和b和b10的不同值可以預先計算爲常數。