Apa teknik sedikit bijak favorit Anda? [Tutup]

Beberapa hari yang lalu, anggota StackExchange Anto bertanya tentang kegunaan yang valid untuk operator bit-wise. Saya menyatakan bahwa menggeser lebih cepat daripada mengalikan dan membagi bilangan bulat dengan kekuatan dua. Anggota StackExchange, Daemin membalas dengan menyatakan bahwa penggeseran-kanan menghadirkan masalah dengan angka negatif.

Pada saat itu, saya tidak pernah benar-benar berpikir untuk menggunakan operator shift dengan bilangan bulat yang ditandatangani. Saya terutama menggunakan teknik ini dalam pengembangan perangkat lunak tingkat rendah; oleh karena itu, saya selalu menggunakan bilangan bulat yang tidak ditandatangani. C melakukan pergeseran logis pada bilangan bulat yang tidak ditandai. Tidak ada perhatian yang diberikan pada bit tanda saat melakukan pergeseran logis dengan benar. Bit yang telah diisi diisi dengan nol. Namun, C melakukan operasi pergeseran aritmatika ketika menggeser bilangan bulat yang ditandatangani. Bit yang terisi diisi dengan bit tanda. Perbedaan ini menyebabkan nilai negatif dibulatkan ke arah infinity alih-alih terpotong ke nol, yang merupakan perilaku yang berbeda dari pembagian integer yang ditandatangani.

Beberapa menit pemikiran menghasilkan solusi tingkat pertama. Solusi secara kondisional mengkonversi nilai negatif ke nilai positif sebelum bergeser. Nilai dikonversi secara kondisional kembali ke bentuk negatif setelah operasi shift telah dilakukan.

int a = -5;
int n = 1;

int negative = q < 0; 

a = negative ? -a : a; 
a >>= n; 
a = negative ? -a : a; 

Masalah dengan solusi ini adalah bahwa pernyataan tugas bersyarat biasanya diterjemahkan ke setidaknya satu instruksi lompatan, dan instruksi lompatan bisa mahal pada prosesor yang tidak men-decode kedua jalur instruksi. Harus memposisikan ulang sebuah pipa instruksi dua kali membuat penyimpangan yang baik dalam setiap perolehan kinerja yang diperoleh dengan bergeser dari pembagian.

Dengan kata di atas, saya bangun pada hari Sabtu dengan jawaban untuk masalah tugas bersyarat. Masalah pembulatan yang kita alami ketika melakukan operasi pergeseran aritmatika hanya terjadi ketika bekerja dengan representasi komplemen dua. Itu tidak terjadi dengan representasi komplemen seseorang. Solusi untuk masalah ini melibatkan konversi nilai komplemen dua menjadi nilai komplemen seseorang sebelum melakukan operasi shift. Kami kemudian harus mengubah nilai komplemen seseorang kembali ke nilai komplemen dua. Anehnya, kita dapat melakukan serangkaian operasi ini tanpa mengubah nilai negatif sebelum melakukan operasi shift.

int a = -5;
int n = 1;

register int sign = (a >> INT_SIZE_MINUS_1) & 1

a = (a - sign) >> n + sign;   

Nilai negatif komplemen dua dikonversi ke nilai negatif komplemen seseorang dengan mengurangi satu. Di sisi lain, nilai negatif komplemen seseorang dikonversi ke nilai negatif komplemen dua dengan menambahkan satu. Kode yang tercantum di atas berfungsi karena bit tanda digunakan untuk mengkonversi dari komplemen dua ke komplemen seseorang dan sebaliknya . Hanya nilai negatif yang akan mengatur bit tanda mereka; oleh karena itu, tanda variabel akan sama dengan nol ketika a positif.

Dengan kata di atas, dapatkah Anda memikirkan peretasan bit-bijaksana lain seperti yang di atas yang telah membuatnya menjadi tas trik Anda? Apa retas bit-bijaksana favorit Anda? Saya selalu mencari peretasan bit-wise-oriented baru.

Saya suka hack Gosper (HAKMEM # 175), cara yang sangat cerdik untuk mengambil nomor dan mendapatkan nomor berikutnya dengan jumlah bit yang sama. Ini berguna, misalnya, dalam menghasilkan kombinasi kitem dari n:

int set = (1 << k) - 1;
int limit = (1 << n);
while (set < limit) {
    doStuff(set);

    // Gosper's hack:
    int c = set & -set;
    int r = set + c;
    set = (((r^set) >>> 2) / c) | r;
}

The Cepat kuadrat terbalik metode akar menggunakan teknik bit-tingkat aneh paling untuk komputasi kebalikan dari akar kuadrat yang pernah saya lihat:

float Q_rsqrt( float number )
{
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
    //    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

    return y;
}

Division by 3 - tanpa menggunakan panggilan perpustakaan run-time.

Ternyata pembagian dengan 3 (berkat petunjuk tentang Stack Overflow) dapat diperkirakan sebagai:

X / 3 = [(x / 4) + (x / 12)]

Dan X / 12 adalah (x / 4) / 3. Ada elemen rekursi yang tiba-tiba muncul di sini.

Ternyata juga jika Anda membatasi rentang angka yang Anda mainkan, Anda dapat membatasi jumlah iterasi yang diperlukan.

Dan dengan demikian, untuk bilangan bulat tak bertanda <2000, berikut ini adalah algoritma cepat dan sederhana / 3. (Untuk angka yang lebih besar, tambahkan saja langkah-langkah lainnya). Compiler mengoptimalkan heck out dari ini sehingga akhirnya menjadi cepat dan kecil:

FastDivide3 pendek unsigned statis (arg unsigned short arg pendek)
{
  RunningSum pendek yang tidak ditandatangani;
  FractionalTwelth singkat yang tidak ditandatangani;

  RunningSum = arg >> 2;

  FractionalTwelth = RunningSum >> 2;
  RunningSum + = FractionalTwelth;

  FractionalTwelth >> = 2;
  RunningSum + = FractionalTwelth;

  FractionalTwelth >> = 2;
  RunningSum + = FractionalTwelth;

  FractionalTwelth >> = 2;
  RunningSum + = FractionalTwelth;

  // Lebih banyak pengulangan dari 2 baris di atas untuk lebih presisi

  mengembalikan RunningSum;
}

Jika Anda melihat di Erlang ada seluruh DSL untuk melakukan operasi bit. JADI, Anda bisa memecah struktur data dengan bit dengan mengatakan sesuatu seperti ini:

<> = << 1,17,42: 16 >>.

Detail lengkapnya di sini: http://www.erlang.org/doc/reference_manual/expressions.html#id75782