Bagaimana untuk Mendapatkan Separuh Atas Pendaraban Integer 64-bit dalam C?

Mendapatkan Separuh Atas Pendaraban Integer 64-bit

Dalam C , pendaraban dua integer 64-bit (uint64_t) menghasilkan nilai yang mewakili 64 bit bawah produk, iaitu, (i * j) mod (2^64). Untuk mendapatkan 64 bit atas, pelbagai pendekatan boleh digunakan.

Menggunakan Nombor 128-bit

Jika pengkompil anda menyokong integer 128-bit (__uint128_t), paling banyak pendekatan yang cekap adalah dengan melakukan pendaraban menggunakan aritmetik 128-bit dan mengekstrak 64 atas bit.

Pendekatan Mudah Alih untuk Aritmetik 64-bit

Untuk penyusun yang tidak menyokong nombor 128-bit, penyelesaian mudah alih adalah untuk memisahkan setiap integer 64-bit kepada dua bahagian 32-bit dan darabnya menggunakan pendaraban 64-bit. Bahagian atas dan bahagian bawah kemudiannya digabungkan untuk mengira produk 128-bit penuh.

Walau bagaimanapun, pengiraan ini boleh mengakibatkan limpahan apabila menggunakan aritmetik 64-bit. Kod di bawah menyediakan pelaksanaan yang mengendalikan limpahan semasa mengira 64 bit atas:

uint64_t mulhi(uint64_t a, uint64_t b) {
    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;

    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;
}

Perhatikan bahawa mengabaikan pengiraan carry_bit akan menyebabkan nilai 64-bit atas yang mungkin dimatikan sebanyak 1.

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