Saya melihat teknik yang menarik digunakan dalam jawaban untuk pertanyaan lain , dan ingin mengerti sedikit lebih baik.
Kami diberi integer 64-bit yang tidak ditandatangani, dan kami tertarik pada bit berikut:
1.......2.......3.......4.......5.......6.......7.......8.......
Secara khusus, kami ingin memindahkan mereka ke posisi delapan besar, seperti:
12345678........................................................
Kami tidak peduli tentang nilai bit yang ditunjukkan oleh .
, dan mereka tidak harus dipertahankan.
The solusi adalah untuk menutupi keluar bit yang tidak diinginkan, dan kalikan hasilnya dengan 0x2040810204081
. Ternyata ini yang berhasil.
Seberapa umum metode ini? Bisakah teknik ini digunakan untuk mengekstrak setiap subset bit? Jika tidak, bagaimana cara mengetahui apakah metode ini bekerja untuk set bit tertentu atau tidak?
Akhirnya, bagaimana cara mencari pengganda (a?) Yang benar untuk mengekstrak bit yang diberikan?
Jawaban:
Pertanyaan yang sangat menarik, dan trik cerdik.
Mari kita lihat contoh sederhana untuk memanipulasi byte tunggal. Menggunakan unsigned 8 bit untuk kesederhanaan. Bayangkan nomor Anda
xxaxxbxx
Anda dan yang Anda inginkanab000000
.Solusinya terdiri dari dua langkah: sedikit masking, diikuti oleh perkalian. Topeng bit adalah operasi DAN sederhana yang mengubah bit tidak menarik menjadi nol. Dalam kasus di atas, topeng Anda akan menjadi
00100100
dan hasilnya00a00b00
.Sekarang bagian yang sulit: mengubahnya menjadi
ab......
.Perkalian adalah sekelompok operasi shift-and-add. Kuncinya adalah membiarkan overflow untuk "mengalihkan" bit yang tidak kita butuhkan dan meletakkan bit yang kita inginkan di tempat yang tepat.
Perkalian dengan 4 (
00000100
) akan menggeser semua yang tersisa 2 dan membuat Anda melakukannyaa00b0000
. Untuk mendapatkanb
naik, kita perlu mengalikan dengan 1 (untuk menjaga a di tempat yang tepat) + 4 (untuk memindahkan b ke atas). Jumlah ini adalah 5, dan dikombinasikan dengan 4 sebelumnya kita mendapatkan angka ajaib 20, atau00010100
. Yang asli00a00b00
setelah topeng; perkalian memberikan:Dari pendekatan ini Anda dapat memperluas ke jumlah yang lebih besar dan lebih banyak bit.
Salah satu pertanyaan yang Anda ajukan adalah "dapatkah ini dilakukan dengan sejumlah bit?" Saya pikir jawabannya adalah "tidak", kecuali jika Anda mengizinkan beberapa operasi masking, atau beberapa perkalian. Masalahnya adalah masalah "tabrakan" - misalnya, "nyasar b" dalam masalah di atas. Bayangkan kita perlu melakukan ini ke nomor seperti
xaxxbxxcx
. Mengikuti pendekatan sebelumnya, Anda akan berpikir kita perlu {x 2, x {1 + 4 + 16}} = x 42 (oooh - jawaban untuk semuanya!). Hasil:Seperti yang Anda lihat, itu masih berfungsi, tetapi "hanya". Kuncinya di sini adalah bahwa ada "ruang yang cukup" antara bit yang kita inginkan sehingga kita bisa menekan semuanya. Saya tidak bisa menambahkan bit keempat d tepat setelah c, karena saya akan mendapatkan contoh di mana saya mendapatkan c + d, bit mungkin membawa ...
Jadi tanpa bukti formal, saya akan menjawab bagian yang lebih menarik dari pertanyaan Anda sebagai berikut: "Tidak, ini tidak akan bekerja untuk sejumlah bit. Untuk mengekstrak N bit, Anda perlu (N-1) spasi antara bit yang ingin Anda mengekstrak, atau memiliki langkah-langkah mask-multiply tambahan. "
Satu-satunya pengecualian yang dapat saya pikirkan untuk aturan "harus memiliki (N-1) nol di antara bit" adalah ini: jika Anda ingin mengekstrak dua bit yang berdekatan satu sama lain di aslinya, DAN Anda ingin menyimpannya di urutan yang sama, maka Anda masih bisa melakukannya. Dan untuk tujuan aturan (N-1) mereka menghitung sebagai dua bit.
Ada wawasan lain - terinspirasi oleh jawaban @Ternary di bawah ini (lihat komentar saya di sana). Untuk setiap bit yang menarik, Anda hanya perlu sebanyak nol di sebelah kanan karena Anda membutuhkan ruang untuk bit yang perlu pergi ke sana. Tetapi juga, dibutuhkan sebanyak bit ke kiri karena memiliki bit hasil ke kiri. Jadi, jika sedikit b berakhir di posisi m dari n, maka perlu memiliki m-1 nol di sebelah kirinya, dan nm nol di sebelah kanan. Terutama ketika bit tidak dalam urutan yang sama dengan nomor aslinya seperti yang akan setelah pemesanan ulang, ini merupakan peningkatan penting untuk kriteria asli. Ini berarti, misalnya, kata yang 16 bit
Dapat digeser menjadi
meskipun hanya ada satu ruang antara e dan b, dua antara d dan c, tiga antara yang lain. Apa yang terjadi dengan N-1 ?? Dalam hal ini,
a...e
menjadi "satu blok" - mereka dikalikan dengan 1 untuk berakhir di tempat yang tepat, jadi "kami mendapat e gratis". Hal yang sama berlaku untuk b dan d (b membutuhkan tiga ruang ke kanan, d membutuhkan tiga yang sama ke kiri). Jadi ketika kami menghitung angka ajaib, kami menemukan ada duplikat:Jelas, jika Anda menginginkan angka-angka ini dalam urutan yang berbeda, Anda harus menempatkannya lebih jauh. Kita dapat merumuskan kembali
(N-1)
aturan: "Itu akan selalu bekerja jika ada setidaknya (N-1) ruang antara bit; atau, jika urutan bit dalam hasil akhir diketahui, maka jika bit b berakhir di posisi m dari n, harus memiliki m-1 nol di sebelah kiri, dan nm nol di sebelah kanan. "@Ternary menunjukkan bahwa aturan ini tidak berfungsi, karena mungkin ada carry dari bit yang menambahkan "tepat di sebelah kanan area target" - yaitu, ketika bit yang kita cari adalah semuanya. Melanjutkan contoh yang saya berikan di atas dengan lima bit yang dikemas dalam kata 16 bit: jika kita mulai dengan
Untuk kesederhanaan, saya akan menyebutkan posisi bit
ABCDEFGHIJKLMNOP
Matematika yang akan kami lakukan adalah
Sampai sekarang, kami pikir apa pun di bawah ini
abcde
(posisiABCDE
) tidak masalah, tetapi pada kenyataannya, seperti yang ditunjukkan @Ternary, jikab=1, c=1, d=1
kemudian(b+c)
dalam posisiG
akan menyebabkan sedikit untuk dibawa ke posisiF
, yang berarti bahwa(d+1)
dalam posisiF
akan membawa sedikit ke dalamE
- dan kami hasilnya rusak. Perhatikan bahwa ruang di sebelah kanan sedikit kepentingan paling signifikan (c
dalam contoh ini) tidak masalah, karena penggandaan akan menyebabkan padding dengan nol dari sebelumnya bit paling tidak signifikan.Jadi kita perlu memodifikasi aturan (m-1) / (nm) kita. Jika ada lebih dari satu bit yang memiliki "persis (nm) bit yang tidak digunakan ke kanan (tidak termasuk bit terakhir dalam pola -" c "pada contoh di atas), maka kita perlu memperkuat aturan - dan kita harus lakukan secara iteratif!
Kita harus melihat tidak hanya pada jumlah bit yang memenuhi kriteria (nm), tetapi juga yang ada pada (n-m + 1), dll. Mari kita sebut nomor mereka Q0 (tepat
n-m
untuk bit berikutnya), Q1 ( n-m + 1), hingga Q (N-1) (n-1). Maka kita berisiko membawa jikaJika Anda melihat ini, Anda dapat melihat bahwa jika Anda menulis ekspresi matematika sederhana
dan hasilnya adalah
W > 2 * N
, maka Anda perlu meningkatkan kriteria RHS sedikit demi sedikit(n-m+1)
. Pada titik ini, operasi aman selamaW < 4
; jika itu tidak berhasil, tambah satu kriteria lagi, dll.Saya pikir mengikuti hal di atas akan membuat Anda jauh ke jawaban Anda ...
sumber
Pertanyaan yang sangat menarik. Saya menyinggung dua sen saya, yaitu, jika Anda dapat mengatur untuk menyatakan masalah seperti ini dalam hal logika tingkat pertama atas teori bitvector, maka pembalik teorema adalah teman Anda, dan berpotensi memberi Anda sangat cepat jawaban atas pertanyaan Anda. Mari kita nyatakan kembali masalah yang ditanyakan sebagai teorema:
"Ada beberapa konstanta 64-bit 'mask' dan 'multiplicand' sedemikian rupa sehingga, untuk semua bitvektor 64-bit x, dalam ekspresi y = (x & mask) * multiplicand, kita memiliki y.63 == x.63 , y.62 == x.55, y.61 == x.47, dll. "
Jika kalimat ini sebenarnya adalah teorema, maka memang benar bahwa beberapa nilai konstanta 'topeng' dan 'multiplicand' memenuhi sifat ini. Jadi mari kita frase ini dalam hal sesuatu yang dapat dipahami oleh sebuah teorema teorema, yaitu input SMT-LIB 2:
Dan sekarang mari kita tanyakan pada teorema Z3 apakah ini adalah teorema:
Hasilnya adalah:
Bingo! Ini mereproduksi hasil yang diberikan dalam posting asli dalam 0,06 detik.
Melihat ini dari perspektif yang lebih umum, kita dapat melihat ini sebagai contoh dari masalah sintesis program tingkat pertama, yang merupakan bidang penelitian yang baru muncul tentang beberapa makalah yang telah diterbitkan. Pencarian
"program synthesis" filetype:pdf
harus membantu Anda memulai.sumber
Setiap 1-bit dalam pengali digunakan untuk menyalin salah satu bit ke posisi yang benar:
1
sudah dalam posisi yang benar, jadi kalikan dengan0x0000000000000001
.2
harus digeser posisi 7 bit ke kiri, jadi kita kalikan dengan0x0000000000000080
(bit 7 diatur).3
harus digeser posisi 14 bit ke kiri, jadi kita kalikan dengan0x0000000000000400
(bit 14 diatur).8
harus digeser posisi 49 bit ke kiri, jadi kita kalikan dengan0x0002000000000000
(bit 49 diatur).Pengganda adalah jumlah dari pengganda untuk bit individual.
Ini hanya berfungsi karena bit yang dikumpulkan tidak terlalu berdekatan, sehingga penggandaan bit yang tidak termasuk dalam skema kami berada di luar 64 bit atau di bagian tidak peduli yang lebih rendah.
Perhatikan bahwa bit lain dalam nomor aslinya harus
0
. Ini dapat dicapai dengan menutupi mereka dengan operasi DAN.sumber
(Aku belum pernah melihatnya sebelumnya. Trik ini hebat!)
Saya akan memperluas sedikit pada pernyataan Floris bahwa ketika mengekstraksi
n
bit Anda memerlukann-1
ruang antara bit yang tidak berurutan:Pikiran awal saya (kita akan lihat sebentar lagi bagaimana ini tidak cukup berhasil) adalah bahwa Anda bisa melakukan lebih baik: Jika Anda ingin mengekstrak
n
bit, Anda akan memiliki tabrakan ketika mengekstraksi / menggeser biti
jika Anda memiliki orang lain (non -berjalan dengan biti
) padai-1
bit sebelumnya ataun-i
bit-bit berikutnya.Saya akan memberikan beberapa contoh untuk menggambarkan:
...a..b...c...
Bekerja (tidak ada dalam 2 bit setelaha
, bit sebelum dan sedikit setelahb
, dan tidak ada yang ada di 2 bit sebelumnyac
):...a.b....c...
Gagal karenab
ada dalam 2 bit setelaha
(dan akan ditarik ke tempat orang lain ketika kita bergesera
):...a...b.c...
Gagal karenab
ada dalam 2 bit sebelumnyac
(dan terdorong ke tempat orang lain ketika kita bergeserc
):...a...bc...d...
Bekerja karena bit berturut-turut bergeser bersama:Tapi kami punya masalah. Jika kita menggunakan
n-i
alih-alihn-1
kita dapat memiliki skenario berikut: bagaimana jika kita memiliki tabrakan di luar bagian yang kita pedulikan, sesuatu yang kita akan sembunyikan di bagian akhir, tetapi bit pengangkutnya yang akhirnya mengganggu jangkauan penting tanpa-penutup ? (dan perhatikan:n-1
persyaratan memastikan ini tidak terjadi dengan memastikani-1
bit setelah rentang un-masked kami jelas ketika kami menggeseri
bit th)...a...b..c...d...
Potensi kegagalan pada carry-bit,c
adan-1
setelahnyab
, tetapi memenuhin-i
kriteria:Jadi mengapa kita tidak kembali saja ke
n-1
persyaratan " sedikit ruang" itu? Karena kita dapat melakukan yang lebih baik :...a....b..c...d..
Gagal padan-1
tes " bit of space", tetapi bekerja untuk trik penggalian bit kami:Saya tidak dapat menemukan cara yang baik untuk mengkarakterisasi bidang-bidang ini yang tidak memiliki
n-1
ruang di antara bit-bit penting, tetapi masih akan bekerja untuk operasi kami. Namun, karena kita tahu sebelumnya bit mana yang kami minati, kami dapat memeriksa filter kami untuk memastikan kami tidak mengalami tabrakan carry-bit:Bandingkan
(-1 AND mask) * shift
dengan hasil semua yang diharapkan,-1 << (64-n)
(untuk 64-bit yang tidak ditandatangani)Pergeseran ajaib / gandakan untuk mengekstrak bit kita berfungsi jika dan hanya jika keduanya sama.
sumber
b
berakhir di posisim
darin
, maka perlu memilikim-1
nol ke kiri, dann-m-1
nol ke kanan. Terutama ketika bit tidak dalam urutan yang sama dengan nomor aslinya seperti yang akan setelah pemesanan ulang, ini merupakan peningkatan penting untuk kriteria asli. Ini menyenangkan.Selain jawaban yang sudah sangat bagus untuk pertanyaan yang sangat menarik ini, mungkin berguna untuk mengetahui bahwa trik penggandaan bitwise ini telah dikenal di komunitas catur komputer sejak 2007, di mana ia berjalan dengan nama Magic BitBoards .
Banyak mesin catur komputer menggunakan beberapa bilangan bulat 64-bit (disebut bitboard) untuk mewakili berbagai set piece (1 bit per persegi yang diduduki). Misalkan potongan geser (benteng, uskup, ratu) pada kotak asal tertentu dapat bergerak ke paling banyak
K
kotak jika tidak ada potongan penghalang yang hadir. Menggunakan bitwise-danK
bit - bit yang tersebar dengan bitboard dari kotak yang ditempati memberikanK
kata-bit khusus yang tertanam dalam integer 64-bit.Perkalian ajaib dapat digunakan untuk memetakan
K
bit - bit yang tersebar ini ke bit yang lebih rendahK
dari integer 64-bit.K
Bit-bit yang lebih rendah ini kemudian dapat digunakan untuk mengindeks tabel dari bitboard yang telah dikomputasi sebelumnya yang mewakili kotak yang diizinkan yang dapat dipindahkan oleh potongan pada kuadrat asalnya (merawat blokir potongan dll.)Mesin catur biasa yang menggunakan pendekatan ini memiliki 2 tabel (satu untuk benteng, satu untuk uskup, ratu menggunakan kombinasi keduanya) dari 64 entri (satu per kotak asal) yang berisi hasil yang telah dihitung sebelumnya. Baik sumber tertutup berperingkat tertinggi ( Houdini ) dan mesin catur open source ( Stockfish ) saat ini menggunakan pendekatan ini untuk kinerjanya yang sangat tinggi.
Menemukan pengganda ajaib ini dilakukan baik menggunakan pencarian lengkap (dioptimalkan dengan cutoff awal) atau dengan uji coba dan kesalahan (misalnya mencoba banyak bilangan bulat 64-bit acak). Tidak ada pola bit yang digunakan selama generasi bergerak yang tidak ada konstanta sihir yang dapat ditemukan. Namun, efek carry bitwise biasanya diperlukan ketika bit yang akan dipetakan memiliki (hampir) indeks yang berdekatan.
AFAIK, pendekatan SAT-solver yang sangat umum oleh @Syzygy belum pernah digunakan dalam catur komputer, dan tampaknya juga tidak ada teori formal tentang keberadaan dan keunikan konstanta sihir semacam itu.
sumber