Bagaimana untuk Mengekstrak Bahagian Tinggi Pendaraban Integer 64-bit dalam C?

Mengekstrak Bahagian Tinggi Pendaraban Integer 64-bit

Dalam C , mendarab dua integer 64-bit ( uint64_t ) menghasilkan nilai yang mewakili 64 bit produk ini operasi biasanya digunakan untuk mencapai aritmetik modular, di mana bit yang lebih rendah mengandungi baki yang dikehendaki Walau bagaimanapun, kadangkala, kita juga perlu mengira bahagian bit yang lebih tinggi daripada pendaraban.

Penyelesaian Optimum

Pertimbangkan senario berikut:

uint64_t i = // some value
uint64_t j = // some value
uint64_t k = mulhi(i, j); // where mulhi() returns the higher part of the 64-bit multiplication

Jika menggunakan pengkompil GCC yang menyokong nombor 128-bit, strategi yang paling berkesan adalah Lakukan pendaraban 128-bit dan ekstrak 64 bit atas.

Alternatif tanpa sokongan 128-bit

Jika tiada sokongan 128-bit, anda boleh menggunakan kaedah yang disediakan oleh Yakk. Kaedah ini menguraikan a dan b setiap satu kepada dua nombor 32-bit, dan kemudian menggunakan pendaraban 64-bit untuk mengira hasil darab nombor yang lebih kecil ini masing-masing.

pecah seperti berikut:

uint64_t a_lo = (uint32_t)a;
uint64_t a_hi = a >> 32;
uint64_t b_lo = (uint32_t)b;
uint64_t b_hi = b >> 32;

Kini, produk boleh diwakili sebagai:

a * b = ((a_hi << 32) + a_lo) * ((b_hi << 32) + b_lo)

      = ((a_hi * b_hi) << 64) +
        ((a_hi * b_lo) << 32) +
        ((b_hi * a_lo) << 32) +
          a_lo * b_lo

Walau bagaimanapun, mengira formula di atas menggunakan 64 bit akan menghasilkan limpahan . Oleh itu, kami perlu melakukan pemprosesan khas pada hasil perantaraan:

// 为防止溢出而引入的临时变量
uint64_t a_x_b_hi = a_hi * b_hi;
uint64_t a_x_b_mid = a_hi * b_lo;
uint64_t b_x_a_mid = b_hi * a_lo;
uint64_t a_x_b_lo = a_lo * b_lo;

// 计算进位位
uint64_t carry_bit = (((uint64_t)(uint32_t)a_x_b_mid +
                         (uint64_t)(uint32_t)b_x_a_mid +
                         (a_x_b_lo >> 32)) >> 32);

// 计算高位部分并返回
uint64_t multhi = a_x_b_hi +
                     (a_x_b_mid >> 32) + (b_x_a_mid >> 32) +
                     carry_bit;

return multhi;

Dengan sedikit pengubahsuaian, jika anda tidak mengambil berat tentang tambahan 1 dalam bahagian tertib tinggi, anda boleh meninggalkan pengiraan membawa sedikit.

Atas ialah kandungan terperinci Bagaimana untuk Mengekstrak Bahagian Tinggi Pendaraban Integer 64-bit dalam C?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!