Posisi bit paling tidak signifikan yang ditetapkan

Saya mencari cara yang efisien untuk menentukan posisi bit paling tidak signifikan yang diatur dalam bilangan bulat, misalnya untuk 0x0FF0 akan menjadi 4.

Implementasi sepele adalah ini:

unsigned GetLowestBitPos(unsigned value)
{
   assert(value != 0); // handled separately

   unsigned pos = 0;
   while (!(value & 1))
   {
      value >>= 1;
      ++pos;
   }
   return pos;
}

Ada ide bagaimana memeras beberapa siklus darinya?

(Catatan: pertanyaan ini untuk orang-orang yang menikmati hal-hal seperti itu, bukan untuk orang-orang yang mengatakan bahwa optimasi xyz itu jahat.)

[Sunting] Terima kasih semua orang atas idenya! Saya juga telah mempelajari beberapa hal lain. Keren!

Bit Twiddling Hacks menawarkan koleksi yang sangat baik dari, er, bit twiddling hacks, dengan diskusi kinerja / pengoptimalan terlampir. Solusi favorit saya untuk masalah Anda (dari situs itu) adalah «perbanyak dan cari»:

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

Referensi yang berguna:

• " Using de Bruijn Sequences to Index a 1 in a Computer Word " - Penjelasan tentang mengapa kode di atas berfungsi.
• " Representasi Dewan> Bitboards> BitScan " - Analisis rinci masalah ini, dengan fokus khusus pada pemrograman catur

Mengapa tidak menggunakan ffs bawaan ? (Saya mengambil halaman manual dari Linux, tetapi lebih banyak tersedia dari itu.)

ffs (3) - Halaman manual Linux

Nama

ffs - temukan kumpulan bit pertama dalam sebuah kata

Ringkasan

#include <strings.h>
int ffs(int i);
#define _GNU_SOURCE
#include <string.h>
int ffsl(long int i);
int ffsll(long long int i);

Deskripsi

Fungsi ffs () mengembalikan posisi bit pertama (paling tidak signifikan) yang ditetapkan dalam kata i. Bit yang paling tidak signifikan adalah posisi 1 dan posisi paling signifikan misalnya 32 atau 64. Fungsi ffsll () dan ffsl () melakukan hal yang sama tetapi mengambil argumen dengan ukuran yang mungkin berbeda.

Nilai Kembali

Fungsi ini mengembalikan posisi kumpulan bit pertama, atau 0 jika tidak ada bit yang disetel di i.

Sesuai dengan

4.3BSD, POSIX.1-2001.

Catatan

Sistem BSD memiliki prototipe dalam format <string.h>.

Ada instruksi assembly x86 ( bsf) yang akan melakukannya. :)

Lebih dioptimalkan ?!

Catatan Samping:

Pengoptimalan pada level ini secara inheren bergantung pada arsitektur. Prosesor saat ini terlalu kompleks (dalam hal prediksi cabang, cache miss, pipelining) sehingga sangat sulit untuk memprediksi kode mana yang dieksekusi lebih cepat pada arsitektur mana. Mengurangi operasi dari 32 menjadi 9 atau hal-hal seperti itu bahkan dapat menurunkan kinerja pada beberapa arsitektur. Kode yang dioptimalkan pada satu arsitektur dapat menghasilkan kode yang lebih buruk di arsitektur lain. Saya pikir Anda akan mengoptimalkan ini untuk CPU tertentu atau membiarkannya apa adanya dan membiarkan kompiler memilih apa yang menurutnya lebih baik.

Kebanyakan arsitektur modern memiliki beberapa instruksi untuk menemukan posisi bit set terendah, atau bit set tertinggi, atau menghitung jumlah nol di depan, dll.

Jika Anda memiliki satu instruksi dari kelas ini, Anda dapat dengan murah meniru yang lain.

Luangkan waktu sejenak untuk mengerjakannya di atas kertas dan sadari bahwa itu x & (x-1)akan menghapus bit set terendah dalam x, dan ( x & ~(x-1) )hanya akan mengembalikan bit set terendah, terlepas dari arsitektur, panjang kata, dll. Mengetahui hal ini, sangat mudah menggunakan perangkat keras count-leading -zeroes / tertinggi-set-bit untuk menemukan bit set terendah jika tidak ada instruksi eksplisit untuk melakukannya.

Jika tidak ada dukungan perangkat keras yang relevan sama sekali, implementasi multiply-and-lookup dari count-leading-zero yang diberikan di sini atau salah satu yang ada di halaman Bit Twiddling Hacks dapat dengan mudah dikonversi untuk memberikan bit set terendah menggunakan identitas di atas dan memiliki keuntungan karena tidak memiliki cabang.

Weee, banyak solusi dan bukan patokan yang terlihat. Kalian harus malu pada dirimu sendiri ;-)

Mesin saya adalah Intel i530 (2,9 GHz), menjalankan Windows 7 64-bit. Saya mengkompilasi dengan versi 32-bit dari MinGW.

$ gcc --version
gcc.exe (GCC) 4.7.2

$ gcc bench.c -o bench.exe -std=c99 -Wall -O2
$ bench
Naive loop.         Time = 2.91  (Original questioner)
De Bruijn multiply. Time = 1.16  (Tykhyy)
Lookup table.       Time = 0.36  (Andrew Grant)
FFS instruction.    Time = 0.90  (ephemient)
Branch free mask.   Time = 3.48  (Dan / Jim Balter)
Double hack.        Time = 3.41  (DocMax)

$ gcc bench.c -o bench.exe -std=c99 -Wall -O2 -march=native
$ bench
Naive loop.         Time = 2.92
De Bruijn multiply. Time = 0.47
Lookup table.       Time = 0.35
FFS instruction.    Time = 0.68
Branch free mask.   Time = 3.49
Double hack.        Time = 0.92

Kode saya:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


#define ARRAY_SIZE 65536
#define NUM_ITERS 5000  // Number of times to process array


int find_first_bits_naive_loop(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            if (value == 0)
                continue;
            unsigned pos = 0;
            while (!(value & 1))
            {
                value >>= 1;
                ++pos;
            }
            total += pos + 1;
        }
    }

    return total;
}


int find_first_bits_de_bruijn(unsigned nums[ARRAY_SIZE])
{
    static const int MultiplyDeBruijnBitPosition[32] = 
    {
       1, 2, 29, 3, 30, 15, 25, 4, 31, 23, 21, 16, 26, 18, 5, 9, 
       32, 28, 14, 24, 22, 20, 17, 8, 27, 13, 19, 7, 12, 6, 11, 10
    };

    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned int c = nums[i];
            total += MultiplyDeBruijnBitPosition[((unsigned)((c & -c) * 0x077CB531U)) >> 27];
        }
    }

    return total;
}


unsigned char lowestBitTable[256];
int get_lowest_set_bit(unsigned num) {
    unsigned mask = 1;
    for (int cnt = 1; cnt <= 32; cnt++, mask <<= 1) {
        if (num & mask) {
            return cnt;
        }
    }

    return 0;
}
int find_first_bits_lookup_table(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned int value = nums[i];
            // note that order to check indices will depend whether you are on a big 
            // or little endian machine. This is for little-endian
            unsigned char *bytes = (unsigned char *)&value;
            if (bytes[0])
                total += lowestBitTable[bytes[0]];
            else if (bytes[1])
              total += lowestBitTable[bytes[1]] + 8;
            else if (bytes[2])
              total += lowestBitTable[bytes[2]] + 16;
            else
              total += lowestBitTable[bytes[3]] + 24;
        }
    }

    return total;
}


int find_first_bits_ffs_instruction(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            total +=  __builtin_ffs(nums[i]);
        }
    }

    return total;
}


int find_first_bits_branch_free_mask(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            int i16 = !(value & 0xffff) << 4;
            value >>= i16;

            int i8 = !(value & 0xff) << 3;
            value >>= i8;

            int i4 = !(value & 0xf) << 2;
            value >>= i4;

            int i2 = !(value & 0x3) << 1;
            value >>= i2;

            int i1 = !(value & 0x1);

            int i0 = (value >> i1) & 1? 0 : -32;

            total += i16 + i8 + i4 + i2 + i1 + i0 + 1;
        }
    }

    return total;
}


int find_first_bits_double_hack(unsigned nums[ARRAY_SIZE])
{
    int total = 0; // Prevent compiler from optimizing out the code
    for (int j = 0; j < NUM_ITERS; j++) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            unsigned value = nums[i];
            double d = value ^ (value - !!value); 
            total += (((int*)&d)[1]>>20)-1022; 
        }
    }

    return total;
}


int main() {
    unsigned nums[ARRAY_SIZE];
    for (int i = 0; i < ARRAY_SIZE; i++) {
        nums[i] = rand() + (rand() << 15);
    }

    for (int i = 0; i < 256; i++) {
        lowestBitTable[i] = get_lowest_set_bit(i);
    }


    clock_t start_time, end_time;
    int result;

    start_time = clock();
    result = find_first_bits_naive_loop(nums);
    end_time = clock();
    printf("Naive loop.         Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_de_bruijn(nums);
    end_time = clock();
    printf("De Bruijn multiply. Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_lookup_table(nums);
    end_time = clock();
    printf("Lookup table.       Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_ffs_instruction(nums);
    end_time = clock();
    printf("FFS instruction.    Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_branch_free_mask(nums);
    end_time = clock();
    printf("Branch free mask.   Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);

    start_time = clock();
    result = find_first_bits_double_hack(nums);
    end_time = clock();
    printf("Double hack.        Time = %.2f, result = %d\n", 
        (end_time - start_time) / (double)(CLOCKS_PER_SEC), result);
}

Solusi tercepat (non-intrinsik / non-assembler) untuk ini adalah menemukan byte terendah dan kemudian menggunakan byte itu dalam tabel pencarian 256 entri. Ini memberi Anda kinerja kasus terburuk dari empat instruksi bersyarat dan kasus terbaik 1. Tidak hanya ini jumlah instruksi yang paling sedikit, tetapi juga jumlah cabang yang paling sedikit yang sangat penting pada perangkat keras modern.

Tabel Anda (256 entri 8-bit) harus berisi indeks LSB untuk setiap nomor dalam kisaran 0-255. Anda memeriksa setiap byte dari nilai Anda dan menemukan byte bukan nol terendah, lalu gunakan nilai ini untuk mencari indeks sebenarnya.

Ini memang membutuhkan memori 256-byte, tetapi jika kecepatan fungsi ini sangat penting maka 256-byte itu sangat berharga,

Misalnya

byte lowestBitTable[256] = {
.... // left as an exercise for the reader to generate
};

unsigned GetLowestBitPos(unsigned value)
{
  // note that order to check indices will depend whether you are on a big 
  // or little endian machine. This is for little-endian
  byte* bytes = (byte*)value;
  if (bytes[0])
    return lowestBitTable[bytes[0]];
  else if (bytes[1])
      return lowestBitTable[bytes[1]] + 8;
  else if (bytes[2])
      return lowestBitTable[bytes[2]] + 16;
  else
      return lowestBitTable[bytes[3]] + 24;  
}

OMG baru saja berputar.

Yang kurang dari sebagian besar contoh ini adalah sedikit pemahaman tentang cara kerja semua perangkat keras.

Setiap kali Anda memiliki cabang, CPU harus menebak cabang mana yang akan diambil. Pipa instruksi dimuat dengan instruksi yang mengarah ke jalur yang ditebak. Jika CPU salah menebak maka pipa instruksi akan dibilas, dan cabang lainnya harus dimuat.

Pertimbangkan loop sementara di bagian atas. Tebakannya adalah tetap berada dalam lingkaran. Ini akan salah setidaknya sekali ketika meninggalkan lingkaran. Ini AKAN menyiram pipa instruksi. Perilaku ini sedikit lebih baik daripada menebak bahwa ia akan meninggalkan loop, dalam hal ini ia akan membuang pipa instruksi pada setiap iterasi.

Jumlah siklus CPU yang hilang sangat bervariasi dari satu jenis prosesor ke prosesor berikutnya. Tetapi Anda dapat mengharapkan antara 20 dan 150 siklus CPU yang hilang.

Grup lebih buruk berikutnya adalah di mana Anda berpikir Anda akan menyimpan beberapa iterasi dengan membagi nilai menjadi potongan-potongan yang lebih kecil dan menambahkan beberapa cabang lagi. Masing-masing cabang ini menambahkan peluang tambahan untuk menyiram pipa instruksi dan menghabiskan 20 hingga 150 siklus jam lagi.

Mari kita pertimbangkan apa yang terjadi ketika Anda mencari nilai dalam tabel. Kemungkinan nilainya saat ini tidak ada di cache, setidaknya bukan pertama kali fungsi Anda dipanggil. Artinya, CPU terhenti saat nilainya dimuat dari cache. Sekali lagi ini bervariasi dari satu mesin ke mesin berikutnya. Chip Intel yang baru benar-benar menggunakan ini sebagai kesempatan untuk menukar utas sementara utas saat ini sedang menunggu pemuatan cache selesai. Ini bisa dengan mudah menjadi lebih mahal daripada penyiraman pipa instruksi, namun jika Anda melakukan operasi ini beberapa kali kemungkinan hanya terjadi sekali.

Jelas solusi waktu konstan tercepat adalah yang melibatkan matematika deterministik. Solusi murni dan elegan.

Saya mohon maaf jika ini sudah ditutup.

Setiap kompiler yang saya gunakan, kecuali XCODE AFAIK, memiliki intrinsik kompiler untuk forward bitscan dan reverse bitscan. Ini akan mengkompilasi ke instruksi perakitan tunggal pada sebagian besar perangkat keras tanpa Cache Miss, tanpa Cabang Miss-Prediction dan Tidak ada pemrogram lain yang menghasilkan batu sandungan.

Untuk kompiler Microsoft, gunakan _BitScanForward & _BitScanReverse.
Untuk GCC, gunakan __builtin_ffs, __builtin_clz, __builtin_ctz.

Selain itu, mohon jangan memposting jawaban dan berpotensi menyesatkan pendatang baru jika Anda tidak memiliki cukup pengetahuan tentang subjek yang sedang dibahas.

Maaf saya benar-benar lupa memberikan solusi .. Ini adalah kode yang saya gunakan di iPad yang tidak memiliki instruksi tingkat perakitan untuk tugas tersebut:

unsigned BitScanLow_BranchFree(unsigned value)
{
    bool bwl = (value & 0x0000ffff) == 0;
    unsigned I1 = (bwl * 15);
    value = (value >> I1) & 0x0000ffff;

    bool bbl = (value & 0x00ff00ff) == 0;
    unsigned I2 = (bbl * 7);
    value = (value >> I2) & 0x00ff00ff;

    bool bnl = (value & 0x0f0f0f0f) == 0;
    unsigned I3 = (bnl * 3);
    value = (value >> I3) & 0x0f0f0f0f;

    bool bsl = (value & 0x33333333) == 0;
    unsigned I4 = (bsl * 1);
    value = (value >> I4) & 0x33333333;

    unsigned result = value + I1 + I2 + I3 + I4 - 1;

    return result;
}

Hal yang perlu dipahami di sini adalah bahwa bukan pembanding yang mahal, tetapi cabang yang muncul setelah pembandingan. Perbandingan dalam kasus ini dipaksa menjadi nilai 0 atau 1 dengan .. == 0, dan hasilnya digunakan untuk menggabungkan matematika yang akan terjadi di kedua sisi cabang.

Edit:

Kode di atas rusak total. Kode ini berfungsi dan masih bebas cabang (jika dioptimalkan):

int BitScanLow_BranchFree(ui value)
{
    int i16 = !(value & 0xffff) << 4;
    value >>= i16;

    int i8 = !(value & 0xff) << 3;
    value >>= i8;

    int i4 = !(value & 0xf) << 2;
    value >>= i4;

    int i2 = !(value & 0x3) << 1;
    value >>= i2;

    int i1 = !(value & 0x1);

    int i0 = (value >> i1) & 1? 0 : -32;

    return i16 + i8 + i4 + i2 + i1 + i0;
}

Ini mengembalikan -1 jika diberikan 0. Jika Anda tidak peduli tentang 0 atau senang mendapatkan 31 untuk 0, hapus kalkulasi i0, menghemat waktu.

Terinspirasi oleh posting serupa ini yang melibatkan pencarian sedikit, saya menawarkan yang berikut:

unsigned GetLowestBitPos(unsigned value)
{
   double d = value ^ (value - !!value); 
   return (((int*)&d)[1]>>20)-1023; 
}

Kelebihan:

• tidak ada loop
• tidak ada percabangan
• berjalan dalam waktu yang konstan
• menangani nilai = 0 dengan mengembalikan hasil di luar batas
• hanya dua baris kode

Kekurangan:

• mengasumsikan sedikit ketangguhan sebagai kode (dapat diperbaiki dengan mengubah konstanta)
• mengasumsikan bahwa double adalah float IEEE * 8 nyata (IEEE 754)

Pembaruan: Seperti yang ditunjukkan di komentar, serikat pekerja adalah implementasi yang lebih bersih (untuk C, setidaknya) dan akan terlihat seperti:

unsigned GetLowestBitPos(unsigned value)
{
    union {
        int i[2];
        double d;
    } temp = { .d = value ^ (value - !!value) };
    return (temp.i[1] >> 20) - 1023;
}

Ini mengasumsikan int 32-bit dengan penyimpanan little-endian untuk semuanya (pikirkan prosesor x86).

Ini dapat dilakukan dengan kasus terburuk kurang dari 32 operasi:

Prinsip: Memeriksa 2 bit atau lebih sama efisiennya dengan memeriksa 1 bit.

Jadi misalnya tidak ada yang menghentikan Anda untuk memeriksa pengelompokan mana yang pertama, kemudian memeriksa setiap bit dari yang terkecil hingga terbesar dalam kelompok itu.

Jadi ...
jika Anda memeriksa 2 bit sekaligus, Anda memiliki kasus terburuk (Nbits / 2) + 1 total pemeriksaan.
jika Anda memeriksa 3 bit pada satu waktu yang Anda miliki dalam kasus terburuk (Nbits / 3) + 2 pemeriksaan total.
...

Optimal akan memeriksa dalam kelompok 4. Yang akan membutuhkan dalam kasus terburuk 11 operasi alih-alih 32 Anda.

Kasus terbaik beralih dari 1 pemeriksaan algoritme Anda ke 2 pemeriksaan jika Anda menggunakan ide pengelompokan ini. Tetapi 1 cek ekstra dalam kasus terbaik itu sepadan untuk penghematan kasus terburuk.

Catatan: Saya menuliskannya secara penuh daripada menggunakan loop karena cara itu lebih efisien.

int getLowestBitPos(unsigned int value)
{
    //Group 1: Bits 0-3
    if(value&0xf)
    {
        if(value&0x1)
            return 0;
        else if(value&0x2)
            return 1;
        else if(value&0x4)
            return 2;
        else
            return 3;
    }

    //Group 2: Bits 4-7
    if(value&0xf0)
    {
        if(value&0x10)
            return 4;
        else if(value&0x20)
            return 5;
        else if(value&0x40)
            return 6;
        else
            return 7;
    }

    //Group 3: Bits 8-11
    if(value&0xf00)
    {
        if(value&0x100)
            return 8;
        else if(value&0x200)
            return 9;
        else if(value&0x400)
            return 10;
        else
            return 11;
    }

    //Group 4: Bits 12-15
    if(value&0xf000)
    {
        if(value&0x1000)
            return 12;
        else if(value&0x2000)
            return 13;
        else if(value&0x4000)
            return 14;
        else
            return 15;
    }

    //Group 5: Bits 16-19
    if(value&0xf0000)
    {
        if(value&0x10000)
            return 16;
        else if(value&0x20000)
            return 17;
        else if(value&0x40000)
            return 18;
        else
            return 19;
    }

    //Group 6: Bits 20-23
    if(value&0xf00000)
    {
        if(value&0x100000)
            return 20;
        else if(value&0x200000)
            return 21;
        else if(value&0x400000)
            return 22;
        else
            return 23;
    }

    //Group 7: Bits 24-27
    if(value&0xf000000)
    {
        if(value&0x1000000)
            return 24;
        else if(value&0x2000000)
            return 25;
        else if(value&0x4000000)
            return 26;
        else
            return 27;
    }

    //Group 8: Bits 28-31
    if(value&0xf0000000)
    {
        if(value&0x10000000)
            return 28;
        else if(value&0x20000000)
            return 29;
        else if(value&0x40000000)
            return 30;
        else
            return 31;
    }

    return -1;
}

Mengapa tidak menggunakan pencarian biner ? Ini akan selalu selesai setelah 5 operasi (dengan asumsi ukuran int 4 byte):

if (0x0000FFFF & value) {
    if (0x000000FF & value) {
        if (0x0000000F & value) {
            if (0x00000003 & value) {
                if (0x00000001 & value) {
                    return 1;
                } else {
                    return 2;
                }
            } else {
                if (0x0000004 & value) {
                    return 3;
                } else {
                    return 4;
                }
            }
        } else { ...
    } else { ...
} else { ...

Metode lain (pembagian modulus dan pencarian) layak mendapat perhatian khusus di sini dari tautan yang sama yang disediakan oleh @ anton-tykhyy. Metode ini sangat mirip dalam performanya dengan metode penggandaan dan pencarian DeBruijn dengan sedikit perbedaan namun penting.

divisi modulus dan pencarian

 unsigned int v;  // find the number of trailing zeros in v
    int r;           // put the result in r
    static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
    {
      32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
      7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
      20, 8, 19, 18
    };
    r = Mod37BitPosition[(-v & v) % 37];

pembagian modulus dan metode pencarian mengembalikan nilai yang berbeda untuk v = 0x00000000 dan v = FFFFFFFF sedangkan metode perkalian dan pencarian DeBruijn mengembalikan nol pada kedua input.

uji:-

unsigned int n1=0x00000000, n2=0xFFFFFFFF;

MultiplyDeBruijnBitPosition[((unsigned int )((n1 & -n1) * 0x077CB531U)) >> 27]); /* returns 0 */
MultiplyDeBruijnBitPosition[((unsigned int )((n2 & -n2) * 0x077CB531U)) >> 27]); /* returns 0 */
Mod37BitPosition[(((-(n1) & (n1))) % 37)]); /* returns 32 */
Mod37BitPosition[(((-(n2) & (n2))) % 37)]); /* returns 0 */

Menurut halaman BitScan Pemrograman Catur dan pengukuran saya sendiri, kurangi dan xor lebih cepat daripada negate dan mask.

(Perhatikan daripada jika Anda akan menghitung nol di belakangnya 0, metode yang saya miliki mengembalikannya 63sedangkan negate dan mask kembali 0.)

Berikut adalah pengurangan 64-bit dan xor:

unsigned long v;  // find the number of trailing zeros in 64-bit v 
int r;            // result goes here
static const int MultiplyDeBruijnBitPosition[64] = 
{
  0, 47, 1, 56, 48, 27, 2, 60, 57, 49, 41, 37, 28, 16, 3, 61,
  54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11, 4, 62,
  46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
  25, 39, 14, 33, 19, 30, 9, 24, 13, 18, 8, 12, 7, 6, 5, 63
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v ^ (v-1)) * 0x03F79D71B4CB0A89U)) >> 58];

Untuk referensi, berikut adalah versi 64-bit dari metode negate and mask:

unsigned long v;  // find the number of trailing zeros in 64-bit v 
int r;            // result goes here
static const int MultiplyDeBruijnBitPosition[64] = 
{
  0, 1, 48, 2, 57, 49, 28, 3, 61, 58, 50, 42, 38, 29, 17, 4,
  62, 55, 59, 36, 53, 51, 43, 22, 45, 39, 33, 30, 24, 18, 12, 5,
  63, 47, 56, 27, 60, 41, 37, 16, 54, 35, 52, 21, 44, 32, 23, 11,
  46, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x03F79D71B4CB0A89U)) >> 58];

Anda dapat memeriksa apakah ada bit urutan bawah yang disetel. Jika demikian maka lihat urutan bawah dari bit yang tersisa. misalnya,:

32bit int - periksa apakah salah satu dari 16 pertama disetel. Jika demikian, periksa apakah salah satu dari 8 yang pertama telah disetel. jika begitu, ....

jika tidak, periksa apakah salah satu dari 16 di atas sudah diatur ..

Pada dasarnya ini adalah pencarian biner.

Lihat jawaban saya di sini untuk mengetahui cara melakukannya dengan satu instruksi x86, kecuali bahwa untuk menemukan bit set yang paling tidak signifikan, Anda akan menginginkan BSFinstruksi ("bit scan forward") daripada BSRdijelaskan di sana.

Namun solusi lain, mungkin bukan yang tercepat, tetapi tampaknya cukup bagus.
Setidaknya tidak memiliki cabang. ;)

uint32 x = ...;  // 0x00000001  0x0405a0c0  0x00602000
x |= x <<  1;    // 0x00000003  0x0c0fe1c0  0x00e06000
x |= x <<  2;    // 0x0000000f  0x3c3fe7c0  0x03e1e000
x |= x <<  4;    // 0x000000ff  0xffffffc0  0x3fffe000
x |= x <<  8;    // 0x0000ffff  0xffffffc0  0xffffe000
x |= x << 16;    // 0xffffffff  0xffffffc0  0xffffe000

// now x is filled with '1' from the least significant '1' to bit 31

x = ~x;          // 0x00000000  0x0000003f  0x00001fff

// now we have 1's below the original least significant 1
// let's count them

x = x & 0x55555555 + (x >>  1) & 0x55555555;
                 // 0x00000000  0x0000002a  0x00001aaa

x = x & 0x33333333 + (x >>  2) & 0x33333333;
                 // 0x00000000  0x00000024  0x00001444

x = x & 0x0f0f0f0f + (x >>  4) & 0x0f0f0f0f;
                 // 0x00000000  0x00000006  0x00000508

x = x & 0x00ff00ff + (x >>  8) & 0x00ff00ff;
                 // 0x00000000  0x00000006  0x0000000d

x = x & 0x0000ffff + (x >> 16) & 0x0000ffff;
                 // 0x00000000  0x00000006  0x0000000d
// least sign.bit pos. was:  0           6          13

unsigned GetLowestBitPos(unsigned value)
{
    if (value & 1) return 1;
    if (value & 2) return 2;
    if (value & 4) return 3;
    if (value & 8) return 4;
    if (value & 16) return 5;
    if (value & 32) return 6;
    if (value & 64) return 7;
    if (value & 128) return 8;
    if (value & 256) return 9;
    if (value & 512) return 10;
    if (value & 1024) return 11;
    if (value & 2048) return 12;
    if (value & 4096) return 13;
    if (value & 8192) return 14;
    if (value & 16384) return 15;
    if (value & 32768) return 16;
    if (value & 65536) return 17;
    if (value & 131072) return 18;
    if (value & 262144) return 19;
    if (value & 524288) return 20;
    if (value & 1048576) return 21;
    if (value & 2097152) return 22;
    if (value & 4194304) return 23;
    if (value & 8388608) return 24;
    if (value & 16777216) return 25;
    if (value & 33554432) return 26;
    if (value & 67108864) return 27;
    if (value & 134217728) return 28;
    if (value & 268435456) return 29;
    if (value & 536870912) return 30;
    return 31;
}

50% dari semua nomor akan ditampilkan di baris pertama kode.

75% dari semua angka akan kembali pada 2 baris kode pertama.

87% dari semua angka akan kembali dalam 3 baris kode pertama.

94% dari semua angka akan kembali dalam 4 baris kode pertama.

97% dari semua angka akan kembali dalam 5 baris kode pertama.

dll.

Saya pikir orang-orang yang mengeluh tentang betapa tidak efisiennya skenario kasus terburuk untuk kode ini tidak memahami betapa langka kondisi itu akan terjadi.

Menemukan trik pintar ini menggunakan 'topeng ajaib' dalam "Seni pemrograman, bagian 4", yang melakukannya dalam waktu O (log (n)) untuk bilangan n-bit. [dengan log (n) spasi ekstra]. Solusi khas yang memeriksa bit set adalah O (n) atau membutuhkan O (n) ruang ekstra untuk tabel pencarian, jadi ini adalah kompromi yang baik.

Masker ajaib:

m0 = (...............01010101)  
m1 = (...............00110011)
m2 = (...............00001111)  
m3 = (.......0000000011111111)
....

Ide kunci: Tidak ada angka nol di belakang di x = 1 * [(x & m0) = 0] + 2 * [(x & m1) = 0] + 4 * [(x & m2) = 0] + ...

int lastSetBitPos(const uint64_t x) {
    if (x == 0)  return -1;

    //For 64 bit number, log2(64)-1, ie; 5 masks needed
    int steps = log2(sizeof(x) * 8); assert(steps == 6);
    //magic masks
    uint64_t m[] = { 0x5555555555555555, //     .... 010101
                     0x3333333333333333, //     .....110011
                     0x0f0f0f0f0f0f0f0f, //     ...00001111
                     0x00ff00ff00ff00ff, //0000000011111111 
                     0x0000ffff0000ffff, 
                     0x00000000ffffffff };

    //Firstly extract only the last set bit
    uint64_t y = x & -x;

    int trailZeros = 0, i = 0 , factor = 0;
    while (i < steps) {
        factor = ((y & m[i]) == 0 ) ? 1 : 0;
        trailZeros += factor * pow(2,i);
        ++i;
    }
    return (trailZeros+1);
}

Jika C ++ 11 tersedia untuk Anda, terkadang kompiler dapat melakukan tugas tersebut untuk Anda :)

constexpr std::uint64_t lssb(const std::uint64_t value)
{
    return !value ? 0 : (value % 2 ? 1 : lssb(value >> 1) + 1);
}

Hasilnya adalah indeks berbasis 1.

Ini sehubungan dengan jawaban @Anton Tykhyy

Berikut adalah implementasi constexpr C ++ 11 saya menghilangkan gips dan menghapus peringatan pada VC ++ 17 dengan memotong hasil 64bit menjadi 32 bit:

constexpr uint32_t DeBruijnSequence[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
};
constexpr uint32_t ffs ( uint32_t value )
{
    return  DeBruijnSequence[ 
        (( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
            >> 27];
}

Untuk mengatasi masalah 0x1 dan 0x0, keduanya mengembalikan 0, Anda dapat melakukan:

constexpr uint32_t ffs ( uint32_t value )
{
    return (!value) ? 32 : DeBruijnSequence[ 
        (( ( value & ( -static_cast<int32_t>(value) ) ) * 0x077CB531ULL ) & 0xFFFFFFFF)
            >> 27];
}

tetapi jika kompilator tidak dapat atau tidak mau melakukan praproses, panggilan itu akan menambahkan beberapa siklus ke kalkulasi.

Terakhir, jika tertarik, berikut daftar statik yang menegaskan untuk memeriksa bahwa kode melakukan apa yang dimaksudkan untuk:

static_assert (ffs(0x1) == 0, "Find First Bit Set Failure.");
static_assert (ffs(0x2) == 1, "Find First Bit Set Failure.");
static_assert (ffs(0x4) == 2, "Find First Bit Set Failure.");
static_assert (ffs(0x8) == 3, "Find First Bit Set Failure.");
static_assert (ffs(0x10) == 4, "Find First Bit Set Failure.");
static_assert (ffs(0x20) == 5, "Find First Bit Set Failure.");
static_assert (ffs(0x40) == 6, "Find First Bit Set Failure.");
static_assert (ffs(0x80) == 7, "Find First Bit Set Failure.");
static_assert (ffs(0x100) == 8, "Find First Bit Set Failure.");
static_assert (ffs(0x200) == 9, "Find First Bit Set Failure.");
static_assert (ffs(0x400) == 10, "Find First Bit Set Failure.");
static_assert (ffs(0x800) == 11, "Find First Bit Set Failure.");
static_assert (ffs(0x1000) == 12, "Find First Bit Set Failure.");
static_assert (ffs(0x2000) == 13, "Find First Bit Set Failure.");
static_assert (ffs(0x4000) == 14, "Find First Bit Set Failure.");
static_assert (ffs(0x8000) == 15, "Find First Bit Set Failure.");
static_assert (ffs(0x10000) == 16, "Find First Bit Set Failure.");
static_assert (ffs(0x20000) == 17, "Find First Bit Set Failure.");
static_assert (ffs(0x40000) == 18, "Find First Bit Set Failure.");
static_assert (ffs(0x80000) == 19, "Find First Bit Set Failure.");
static_assert (ffs(0x100000) == 20, "Find First Bit Set Failure.");
static_assert (ffs(0x200000) == 21, "Find First Bit Set Failure.");
static_assert (ffs(0x400000) == 22, "Find First Bit Set Failure.");
static_assert (ffs(0x800000) == 23, "Find First Bit Set Failure.");
static_assert (ffs(0x1000000) == 24, "Find First Bit Set Failure.");
static_assert (ffs(0x2000000) == 25, "Find First Bit Set Failure.");
static_assert (ffs(0x4000000) == 26, "Find First Bit Set Failure.");
static_assert (ffs(0x8000000) == 27, "Find First Bit Set Failure.");
static_assert (ffs(0x10000000) == 28, "Find First Bit Set Failure.");
static_assert (ffs(0x20000000) == 29, "Find First Bit Set Failure.");
static_assert (ffs(0x40000000) == 30, "Find First Bit Set Failure.");
static_assert (ffs(0x80000000) == 31, "Find First Bit Set Failure.");

Berikut ini satu alternatif sederhana, meskipun mencari log agak mahal.

if(n == 0)
  return 0;
return log2(n & -n)+1;   //Assuming the bit index starts from 1

baru-baru ini saya melihat bahwa perdana menteri singapura memposting program yang dia tulis di facebook, ada satu baris untuk menyebutkannya ..

Logikanya hanyalah "nilai & -nilai", misalkan Anda memiliki 0x0FF0, lalu, 0FF0 & (F00F + 1), yang sama dengan 0x0010, itu berarti 1 terendah ada di bit ke-4 .. :)

Jika Anda memiliki sumber daya, Anda dapat mengorbankan memori untuk meningkatkan kecepatan:

static const unsigned bitPositions[MAX_INT] = { 0, 0, 1, 0, 2, /* ... */ };

unsigned GetLowestBitPos(unsigned value)
{
    assert(value != 0); // handled separately
    return bitPositions[value];
}

Catatan: Tabel ini akan menghabiskan setidaknya 4 GB (16 GB jika kita membiarkan tipe pengembalian sebagai unsigned). Ini adalah contoh perdagangan satu sumber daya terbatas (RAM) dengan yang lain (kecepatan eksekusi).

Jika fungsi Anda perlu tetap portabel dan berjalan secepat mungkin dengan biaya berapa pun, ini adalah cara yang tepat. Di sebagian besar aplikasi dunia nyata, tabel 4GB tidak realistis.