Bagaimanakah anda boleh mendapatkan bahagian tinggi pendaraban integer 64-bit dalam C ?

Mendapatkan Bahagian Tinggi Pendaraban Integer 64-Bit

Dalam C , jika i dan j ialah integer tidak bertanda 64-bit, i * j menghasilkan 64 bit yang lebih rendah daripada produk mereka, iaitu, (i * j) mod 2^64. Untuk mendapatkan bahagian produk yang lebih tinggi, pertimbangkan pendekatan berikut:

Menggunakan 128-Bit Multiply:

Jika pengkompil menyokong integer 128-bit (cth., __uint128_t ), melakukan darab 128-bit dan mengekstrak 64 bit atas ialah kaedah yang paling cekap.

Pendekatan YAK (Menggunakan Darab 32-Bit):

Ini melibatkan memecahkan setiap integer 64-bit kepada dua bahagian 32-bit, mendarabnya menggunakan operasi darab 64-bit dan menggabungkan keputusan:

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 multhi = a_hi * b_hi + (a_hi * b_lo >> 32) + (b_hi * a_lo >> 32) + a_lo * b_lo;

Mengendalikan Limpahan:

Walau bagaimanapun, pengiraan di atas melaksanakan aritmetik 128-bit, yang boleh mengakibatkan limpahan. Untuk mengendalikan ini apabila dihadkan kepada aritmetik 64-bit, pelaksanaan berikut dilaraskan untuk limpahan:

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 = ((uint32_t)a_x_b_mid + (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;

Nota: Jika ralat 1 bit dalam 64 bit atas boleh diterima, pengiraan bit pembawa boleh ditinggalkan.

Atas ialah kandungan terperinci Bagaimanakah anda boleh mendapatkan bahagian tinggi pendaraban integer 64-bit dalam C ?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!