將一個2×32位大整數除以1000

Question

我有很大的數字，時間（微秒）存儲在兩個32位變量中。 我需要幫助，如何將微秒時間更改爲毫秒，所以我可以將結果存儲在32位數中。

更多詳細信息： 我有一次在兩個32位變量。其中一個變量具有更多有效位，而另一個具有更少有效位。這一次的分辨率爲微秒，所以我想把它改成毫秒。那麼如何劃分存儲在兩個變量中的數字。

Answer 1

如果你沒有一個64位的類型，你可以做如下所示：

uint32_t higher, lower; // your input 

lower /= 1000; 
lower += (higher % 1000) * 4294967L; // approximate 2^32/1000 
higher /= 1000; 

如果結果安裝在lower本身，higher應該0。

請注意，@Mikhail指出，這個解決方案是近似的，並且有一個錯誤0.296 * higher + 2毫秒（除非我失去了一些東西）。

---

如果你真的想更好的精度和不關心效率，你可以使用一個位浮點運算的中間，和圓形正確的結果。我懷疑，如果它是值得的：

uint32_t higher, lower; // your input 

// simpler without a helper variable 
if (lower % 1000 >= 500) 
{ 
    lower /= 1000; 
    ++lower; 
} 
else 
    lower /= 1000; 

lower += round((higher % 1000) * 4294967.296); // 2^32/1000 
higher /= 1000; 

你需要include <cmath>爲round()。

作爲一個說明，@米哈伊爾的解決方案在這種情況下可能會更好，並且可能會更快。雖然對我來說太複雜了。

---

如果你有一個64位的類型，可以分割值轉換爲它：

uint64_t whole_number = higher; 
whole_number <<= 32; 
whole_number |= lower; 

然後你就可以使用whole_number如常。

---

請注意，如果您只需要一個差異，在實際分割之前減去這些值會更快。

假設你知道哪個值越大：

uint32_t higher1, lower1; // smaller value 
uint32_t higher2, lower2; // bigger value 

uint32_t del_high = higher2 - higher1; 
uint32_t del_low = lower2 - lower1; 

if (lower2 < lower1) 
    --del_high; 

現在你可以將結果像以前解釋的轉換。或者有一點運氣，del_high將是0（如果差值小於2^32μs），您將得到結果del_low（以μs爲單位）。

Answer 2

假設你不能使用64位int，我建議使用a multiple precision library, like GMP。

Answer 3

最簡單的方法是使用64位整數類型，但我認爲你不能這樣做。既然你希望你的答案是32位整數，那麼微妙的高階值不能大於999，否則在除以1000之後它不適合32位。所以你操作的更大的微秒數是999 * 2^32 + (2^32 - 1) = 4294967295999。它給你13位十進制數字，你可以用double來處理精確的分割。

如果您因爲某種原因被迫僅使用32位整數，MichałGórny的答案給了您一個大約解決方案。例如。對於whole_number = 1234567890123它會給出1234567805的結果。因爲在1000上劃分最大32位int有一個提示。

32位整數具有確切答案的唯一方法是使用長算術。它需要將長數字存儲在可以擴展以存儲提醒的類型中。你必須將你的兩個32位整數分成四個16位數字。之後，您可以將它分爲紙張，並且有足夠的位來存儲提醒。見micro2milli代碼：

#include <iostream> 

typedef unsigned __int32 uint32; 
typedef unsigned __int64 uint64; 

const uint32 MAX_INT = 0xFFFFFFFF; 

uint32 micro2milli(uint32 hi, uint32 lo) 
{ 
    if (hi >= 1000) 
    { 
    throw std::runtime_error("Cannot store milliseconds in uint32!"); 
    } 

    uint32 r = (lo >> 16) + (hi << 16); 
    uint32 ans = r/1000; 
    r = ((r % 1000) << 16) + (lo & 0xFFFF); 
    ans = (ans << 16) + r/1000; 

    return ans; 
} 

uint32 micro2milli_simple(uint32 hi, uint32 lo) 
{ 
    lo /= 1000; 
    return lo + (hi % 1000) * 4294967L; 
} 

void main() 
{ 
    uint64 micro = 1234567890123; 
    uint32 micro_high = micro >> 32; 
    uint32 micro_low = micro & MAX_INT; 

    // 1234567805 
    std::cout << micro2milli_simple(micro_high, micro_low) << std::endl; 
    // 1234567890 
    std::cout << micro2milli(micro_high, micro_low) << std::endl; 
} 

Answer 4

首先，把你的兩個變量爲3個，每個22顯著位。

uint32_t x0 = l & 0x3FFFFF; 
uint32_t x1 = ((l >> 22) | (h << 10)) & 0x3FFFFF; 
uint32_t x2 = h >> 12; 

現在做分裂（有每×10個可用的比特?,和1000 < 2^10 = 1024，所以沒有溢出可能）

uint32_t t2 = x2/1000; 
x1 |= (x2 % 1000) << 22; 
uint32_t t1 = x1/1000; 
x0 |= (x1 % 1000) << 22; 
uint32_t t0 = (x0 + 500)/1000; 
    /* +0 for round down, +500 for round to nearest, +999 for round up */ 

立即放回東西放在一起。

uint32_t r0 = t0 + t1 << 22; 
uint32_t r1 = (t1 >> 10) + (t2 << 12) + (r0 < t0); 

使用相同的技術，但有四個變量控股16位，你可以做到這一點的除數高達65535然後變得更難與32位運算來做到這一點。