Apakah mungkin untuk menulis program C yang mengalikan dua angka tanpa menggunakan operator perkalian dan penambahan?
Saya menemukan ini di Stack Overflow . Tolong bantu programmer miskin ini dengan masalahnya. Dan tolong jangan memberikan jawaban seperti c = a/(1/((float)b))
, yang persis sama dengan c = a*b
. (Dan sudah diberikan sebagai jawaban.)
Jawaban dengan suara terbanyak pada 19 Januari 2014 menang.
Catatan: Ini adalah pertanyaan troll kode . Tolong jangan menganggap pertanyaan dan / atau jawaban dengan serius. Informasi lebih lanjut dalam troll kode .
Jawaban:
Selalu gunakan rekursi
Ilusi adalah cara yang benar!
sumber
??::
tanpa tanda kurung, satu untuk memecahkan masalah tanpa mencoba mengubah aturan;)inc
Fungsi menguji argumennya untuk melihat apakah bit terendah adalah1
; jika demikian, ia memanggil dirinya sendiri pada bit atas dari argumen dan mengembalikan hasilnya dengan bit rendah yang sama yang diperiksa sedang diset0
, sementara jika tidak (yaitu bit terendah adalah0
), ia menggantikannya0
dengan a1
dan mengembalikan hasilnya . Prosesnya sangat mirip dengan apa yang akan Anda lakukan jika Anda menambahkan nilai dengan tangan, digit biner demi digit biner.Anda harus mengkompilasi program setiap kali, tetapi ia melakukan multiplikasi bilangan bulat positif apa pun di versi C atau C ++.
sumber
"%zu"
format string.sizeof(char[A][B])
akan bekerja (kecuali A <= 0 atau B <= 0 atau A * B meluap, dalam hal ini Anda harus mendapatkan jenis kesalahan 'tipe buruk')main(){return sizeof(char[A][B]);}
dan Anda mengkompilasi menggunakancc -DA=6 -DB=7 a.c; ./a.out; echo $?
Jika Anda baik-baik saja dengan sedikit ketidaktepatan, Anda dapat menggunakan metode Monte Carlo :
Contoh:
Saya kira ini cukup bagus;)
sumber
++
operator.-= -1
|= 1
(akan bekerja pada 50% dari angka, 100% dari waktu)printf
peningkatan:printf("%*cc%n\n", count, &count, 'c');
(Mencetak 'c' menghitung kali, lalu 'c' lagi, dan menyimpan jumlah karakter yang dituliskan kembalicount
.Karena Anda tidak menentukan ukuran angka apa, saya berasumsi bahwa yang Anda maksud adalah dua angka satu bit.
Jika Anda ingin implementasi yang efisien secara maksimal, gunakan implementasi kecil berikut:
Perhatikan bahwa masih hanya menerima bit meskipun jenisnya ints implisit - ini membutuhkan lebih sedikit kode, dan karenanya lebih efisien. (Dan ya, itu mengkompilasi.)
sumber
return a && b;
. Lebih pendek, jadi lebih cepat.return a&b;
.#include<stdbool.h>
mendefinisikantrue
danfalse
.#include<stdbool.h>
tampaknya hanya menjadi tiga#define
s yang dapat Anda lakukan sendiri (true
,false
,bool
, dan bendera untuk menandai bahwa itu telah diaktifkan). Anda juga dapat mengambil trik dari salah satu jawaban lain dan menggunakan implisitint
untuk versi "pendek".Berikut ini skrip shell sederhana untuk melakukannya:
PEMBARUAN: Tentu saja, untuk melakukannya dalam C, cukup bungkus
exec("bash", "-c", ...)
. (Terima kasih, AmeliaBR)sumber
%20
untuk menghindari penggunaan+
tanda - tanda.) Tetapi Anda masih perlu mengurai output (dalam C) untuk mendapatkan nilai dari itu. Yang akan sangat rumit, karena output tampaknya berupa gambar, bukan teks. Penguraian HTML plus OCR mungkin menjadikan itu jawaban terbaik untuk masalah ini.Mengapa, mari kita lakukan pencarian separuh rekursif antara INT64_MIN dan INT64_MAX!
PS Itu dengan senang hati akan sigsegv dengan beberapa nilai. ;)
sumber
Sayangnya, ini hanya berfungsi untuk bilangan bulat.
Karena penambahan tidak diizinkan, mari buat operator kenaikan terlebih dahulu:
Selanjutnya, kita harus menangani tandanya. Pertama, temukan bit tanda:
Kemudian ambil tanda dan besarnya setiap argumen. Untuk meniadakan angka dalam komplemen dua, membalikkan semua bit, dan menambahkan satu.
Untuk melipatgandakan dua bilangan bulat positif, kita dapat menggunakan makna geometris perkalian:
troll:
a++
benar - benar dianggap sebagai tambahan? Saya yakin guru itu bermaksud untuk mengizinkannya.<<
sebenarnya perkalian dengan kekuatan dua, sehingga secara teknis harus dianulir.-1
bukan cara terbaik untuk menemukan bit tanda. Bahkan jika tidak ada built-in konstan, Anda bisa melakukan pergantian logis kanan -1, lalu membalikkan semua bit.MIN_INT
(AKAsignBit
) negatif, ini rusak untuk nilai itu. Untungnya, ia masih berfungsi dalam setengah kasus, karenaMIN_INT * [even number]
harus nol.Juga,plusOne
break for-1
, menyebabkan loop tak terbatas kapan saja hasilnya meluap.plusOne
berfungsi dengan baik untuk nilai apa pun. Maaf bila membingungkan.sumber
(x ^ y) | ((x & y) << 1)
tidak bekerja, ia tidak akan menyebarkan carry ketika x atau y dan carry keduanya benar di posisi yang sama :)Berfungsi untuk nomor floating point:
sumber
Semua orang tahu bahwa Python lebih mudah digunakan daripada C. Dan Python memiliki fungsi yang sesuai dengan setiap operator, untuk kasus di mana Anda tidak dapat menggunakan operator. Yang merupakan definisi masalah kita, bukan? Begitu:
sumber
Tidak satu pun dari jawaban lain yang secara teoritis masuk akal. Seperti komentar pertama pada pertanyaan mengatakan:
Kita perlu mendefinisikan penggandaan, dan angka, sebelum jawaban dimungkinkan. Begitu kita lakukan, masalahnya menjadi sepele.
Cara yang paling populer untuk melakukan ini dalam memulai logika matematika adalah dengan membangun ordinal von Neumann di atas teori himpunan ZF , dan kemudian menggunakan aksioma Peano .
Ini diterjemahkan secara alami ke C, dengan asumsi Anda memiliki tipe set yang dapat berisi set lain. Itu tidak harus mengandung apa pun kecuali set, yang membuatnya sepele (tidak ada yang membuat
void*
omong kosong di sebagian besar set perpustakaan), jadi saya akan meninggalkan implementasi sebagai latihan untuk pembaca.Jadi, pertama:
Jika Anda ingin memperluas ini ke integer, rasional, real, surreals, dll., Anda bisa — dengan ketepatan tak terbatas (dengan asumsi Anda memiliki memori dan CPU tak terbatas), untuk melakukan booting. Tetapi seperti yang dikatakan Kroenecker, Tuhan membuat angka-angka alami; semua yang lain adalah pekerjaan manusia, jadi sungguh, mengapa repot-repot?
sumber
Jika Anda menganggap hack a [b] sebagai curang (karena ini benar-benar add), maka ini berfungsi sebagai gantinya. Tapi pencarian tabel juga melibatkan pointer.
Lihat http://en.wikipedia.org/wiki/IBM_1620 - komputer yang benar-benar melakukan penambahan menggunakan tabel pencarian ...
Sesuatu yang memuaskan tentang menggunakan mekanisme tabel untuk 'mempercepat' operasi yang sebenarnya bisa dilakukan dalam satu instruksi.
sumber
*
char (walaupun ini bukan multiplikasi)Saya tidak yakin apa yang merupakan "kecurangan" dalam posting "code troll" ini, tetapi ini mengalikan 2 bilangan bulat sewenang-wenang, pada saat run time, tanpa operator
*
atau+
menggunakan perpustakaan standar (C99).sumber
Solusi troll saya untuk
unsigned int
:sumber
Ada banyak jawaban bagus di sini, tetapi sepertinya tidak banyak yang memanfaatkan fakta bahwa komputer modern benar-benar kuat. Ada banyak unit pemrosesan di sebagian besar CPU, jadi mengapa menggunakan hanya satu? Kami dapat memanfaatkan ini untuk mendapatkan hasil kinerja yang hebat.
Berikut ini contoh penggunaannya:
The
#pragma omp parallel
direktif membuat OpenMP membagi setiap bagian dari untuk loop ke unit eksekusi yang berbeda, jadi kita mengalikan secara paralel!Perhatikan bahwa Anda harus menggunakan
-fopenmp
flag untuk memberi tahu kompiler untuk menggunakan OpenMP.Troll bagian:
for
loop - setiap thread menjalankan loop.answer--
; sebagian besar waktu, itu tidak akan muncul, tetapi kadang-kadang itu akan menyebabkan hasil yang tidak akurat.sumber
Sayangnya, perkalian adalah masalah yang sangat sulit dalam ilmu komputer. Solusi terbaik adalah dengan menggunakan pembagian sebagai gantinya:
sumber
Dalam kehidupan nyata saya biasanya merespons trolling dengan pengetahuan, jadi inilah jawaban yang tidak troll sama sekali. Ini berfungsi untuk semua
int
nilai sejauh yang saya bisa lihat.Ini, sejauh yang saya pahami, sangat mirip dengan bagaimana CPU sebenarnya dapat melakukan penggandaan bilangan bulat. Pertama, kami memastikan bahwa setidaknya salah satu argumen (
a
) positif dengan membalik tanda pada keduanya jikaa
negatif (dan tidak, saya menolak untuk menghitung negasi sebagai semacam penambahan atau perkalian). Kemudianwhile (a)
loop menambahkan salinan bergeserb
ke hasil untuk setiap bit yang diseta
. Thedo
Loop mengimplementasikanr += x
menggunakan dan, xor, dan pergeseran dalam apa yang jelas satu set setengah-penambah, dengan membawa bit dimasukkan kembali kex
sampai tidak ada lagi (CPU nyata akan menggunakan penambah penuh, yang lebih efisien, tetapi C doesn' t memiliki operator yang kami butuhkan untuk ini, kecuali jika Anda menghitung+
operator).sumber
while(a)
loop tidak pernah berakhir.sumber
while(C/A != B || C%A)
?Membuang ini ke dalam campuran:
Dari halaman info .
- Memperkenalkan sesuatu yang sangat tidak dapat diterima atau tidak masuk akal dalam kode yang tidak dapat dihapus tanpa membuang semuanya, membuat jawaban yang sama sekali tidak berguna untuk OP.
- [...] Tujuannya adalah melakukan pekerjaan rumah dalam bahasa yang menurut OP malas mungkin bisa diterima, tetapi masih membuatnya frustrasi.
sumber
sumber
Tentu:
Tapi tentu saja itu curang; jelas dia ingin bisa menyediakan dua nomor, bukan?
sumber
Tidak ada aritmatika seperti aritmatika pointer:
Fungsi ini
f
menerapkan multiplikasi.main
cukup menyebutnya dengan dua argumen.Berfungsi untuk angka negatif juga.
sumber
a
, ya, negatifb
saya rasa tidak. Tapi itu bisa diperbaiki dengan banyak cara kreatif. Paling sederhana adalah sign_a ^ = sign_b, sign_b = 0.C #
Saya pikir pengurangan dan negasi tidak diperbolehkan ... Pokoknya:
sumber
C dengan SSE intrinsics (karena semuanya lebih baik dengan SIMD):
Keuntungan besar dari implementasi ini adalah bahwa ia dapat dengan mudah diadaptasi untuk melakukan 4 perkalian paralel tanpa
*
atau+
jika diperlukan.sumber
sumber
strlen(cg) != a
adalah metode yang sangat trolling untuk menghilangkan--
(membuatnya O (N * N)).Mungkin terlalu cepat :-(
sumber
Versi Haskell ini hanya bekerja dengan bilangan bulat non-negatif, tetapi ia memperbanyak cara anak pertama kali mempelajarinya. Yaitu, 3x4 adalah 3 kelompok yang terdiri dari 4 hal. Dalam hal ini, "hal-hal" yang dihitung adalah takik ('|') pada tongkat.
sumber
Ini dapat bekerja di C99, jika cuaca tepat, dan kompiler Anda mendukung omong kosong yang tidak ditentukan.
sumber
Karena OP tidak meminta C , inilah salah satu dari (Oracle) SQL!
sumber
*
s!Dapat mengandung jejak UD.
sumber
Uji coba:
sumber