Bagaimanakah Saya Boleh Mendapatkan Kedudukan Set Bit Paling Kurang Ketara dalam Integer?

Menentukan Kedudukan Bit Set Paling Kurang Ketara

Dalam pengaturcaraan, menentukan kedudukan bit yang paling tidak ketara (LSB) yang ditetapkan dalam integer boleh menjadi operasi yang berguna. Pelaksanaan remeh melibatkan berulang kali menutup integer dengan 1 dan menganjakkannya ke kanan sehingga hasilnya menjadi bukan sifar, tetapi kaedah ini boleh menjadi perlahan untuk integer yang besar.

Pengoptimuman Berputar Bit

Godam yang berputar-putar memberikan alternatif yang cekap. Satu penggodaman sedemikian, yang dikenali sebagai kaedah "darab dan cari", mengeksploitasi sifat jujukan de Bruijn untuk melaksanakan pengiraan dalam satu langkah.

Pelaksanaan Kod

unsigned int v;  // find the number of trailing zeros in 32-bit v
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

Penjelasan

Kod ini berfungsi dengan mendarab integer v oleh pemalar ajaib dan kemudian melakukan anjakan sedikit pada hasilnya. Tatasusunan MultiplyDeBruijnBitPosition memetakan hasil pendaraban ke kedudukan LSB yang diingini.

Faedah dan Rujukan

Kaedah ini jauh lebih pantas daripada pelaksanaan remeh, terutamanya untuk integer besar. Untuk mendapatkan lebih banyak pandangan dan penerangan terperinci tentang teknik ini, rujuk:

• "Menggunakan Urutan de Bruijn untuk Mengindeks 1 dalam Perkataan Komputer"
• "Perwakilan Papan > Papan Bit > BitScan"

Atas ialah kandungan terperinci Bagaimanakah Saya Boleh Mendapatkan Kedudukan Set Bit Paling Kurang Ketara dalam Integer?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!