Bagaimana cara menulis program C untuk perkalian tanpa menggunakan operator * dan +?

68

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 . Tolong jangan menganggap pertanyaan dan / atau jawaban dengan serius. Informasi lebih lanjut dalam troll kode .

s3lph
sumber
2
@PaulR gunakan fantasi Anda
John Dvorak
26
Code-golf.SE seharusnya tidak menjadi tempat bagi Anda untuk mengejek pertanyaan yang Anda lihat di StackOverflow.
Gareth
17
@ Gareth, apakah Anda yakin? Baris pertama ini menunjukkan ini mungkin cukup tepat.
Darren Stone
5
Saya sedang menunggu seseorang menulis algoritma berdasarkan sleep
kb_sou
21
Pertanyaan ini tidak konyol seperti kedengarannya. Perangkat keras komputer aktual (transistor) tidak memiliki banyak dan menambah operasi - mereka memiliki operasi logika dasar seperti BUKAN, DAN, ATAU, XOR. Mencari tahu bagaimana menjawab pertanyaan ini dapat memberi Anda wawasan yang sangat baik tentang bagaimana komputer benar-benar bekerja di tingkat gerbang logika.
Gabe

Jawaban:

147

Selalu gunakan rekursi

Ilusi adalah cara yang benar!

int inc(int x) {
    return x&1?inc(x>>1)<<1:x|1;
}

int dec(int x) {
    return x&1?x^1:dec(x>>1)<<1|1;
}

int add(int x, int y) {
    return x?add(dec(x),inc(y)):y;
}

int mul(int x, int y) {
    return x?x^1?add(y,mul(dec(x),y)):y:0;
}

int main() {
    int a, b;
    scanf("%i\n%i", &a, &b);
    printf("%i", mul(a,b));
}
Oberon
sumber
8
Saya akan memberi +3 jika saya bisa: satu untuk rekursi akhir, satu untuk ??::tanpa tanda kurung, satu untuk memecahkan masalah tanpa mencoba mengubah aturan;)
yo '
10
Jika Picasso adalah seorang programmer ...
R Hughes
4
@ SargeBorsch Tapi di mana kesenangan itu ?
Oberon
3
@HC_ incFungsi menguji argumennya untuk melihat apakah bit terendah adalah 1; jika demikian, ia memanggil dirinya sendiri pada bit atas dari argumen dan mengembalikan hasilnya dengan bit rendah yang sama yang diperiksa sedang diset 0, sementara jika tidak (yaitu bit terendah adalah 0), ia menggantikannya 0dengan a 1dan mengembalikan hasilnya . Prosesnya sangat mirip dengan apa yang akan Anda lakukan jika Anda menambahkan nilai dengan tangan, digit biner demi digit biner.
JAB
2
Bukankah fungsi kenaikan masuk ke loop tak terbatas untuk -1? (0xFFFF) ideone menunjukkan (-1 >> 1) == -1.
Destrictor
87

Anda harus mengkompilasi program setiap kali, tetapi ia melakukan multiplikasi bilangan bulat positif apa pun di versi C atau C ++.

 #define A 45  // first number
 #define B 315 // second number

 typedef char buffer[A][B];

 main() {
    printf("%d\n",sizeof(buffer));
 }
Mark Lakata
sumber
4
Letakkan di dalam struktur dan Anda tidak perlu memori.
Ben Jackson
4
Hahahah bagus !!
Almo
1
gunakan "%zu"format string.
Grijesh Chauhan
5
hanya 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')
greggo
3
@ DavidRicherby - Saya bisa menyederhanakan kode main(){return sizeof(char[A][B]);}dan Anda mengkompilasi menggunakancc -DA=6 -DB=7 a.c; ./a.out; echo $?
Mark Lakata
47

Jika Anda baik-baik saja dengan sedikit ketidaktepatan, Anda dapat menggunakan metode Monte Carlo :

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

unsigned int mul(unsigned short a, unsigned short b) {
  const int totalBits = 24;
  const int total = (1 << totalBits);
  const int maxNumBits = 10;
  const int mask = (1 << maxNumBits) - 1;
  int count = 0, i;
  unsigned short x, y;
  for(i = 0; i < total; i++) {
    x = random() & mask;
    y = random() & mask;
    if ((x < a) && (y < b))
      count++;
  }
  return ((long)count) >> (totalBits - (maxNumBits << 1));
}

void main(int argc, char *argv[]) {
  unsigned short a = atoi(argv[1]);
  unsigned short b = atoi(argv[2]);
  printf("%hd * %hd = %d\n", a, b, mul(a, b));
}

Contoh:

$ ./mul 300 250
300 * 250 = 74954

Saya kira ini cukup bagus;)

Petr Pudlák
sumber
3
Anda memiliki suara saya. Saya mendengar Monte Carlo adalah apa yang digunakan NASA untuk perhitungannya. Tapi saya ingin melihat ini tanpa dua contoh ++operator.
Darren Stone
1
@DarrenStone-= -1
Timtech
20
@Timtech |= 1(akan bekerja pada 50% dari angka, 100% dari waktu)
Darren Stone
2
+1, tetapi mencatat bahwa ini bisa terlalu lambat, dan Anda dapat menambahkan dukungan multi-utas, dengan hati-hati mengunci 'hitungan ++' :-)
greggo
1
Selalu ada printfpeningkatan: printf("%*cc%n\n", count, &count, 'c');(Mencetak 'c' menghitung kali, lalu 'c' lagi, dan menyimpan jumlah karakter yang dituliskan kembali count.
MSalters
45

Karena Anda tidak menentukan ukuran angka apa, saya berasumsi bahwa yang Anda maksud adalah dua angka satu bit.

#include <stdbool.h>
bool mul(bool a, bool b) {
    if (a && b) {
        return true;
    } else {
        return false;
    }
}

Jika Anda ingin implementasi yang efisien secara maksimal, gunakan implementasi kecil berikut:

m(a,b){return a&b;}

Perhatikan bahwa masih hanya menerima bit meskipun jenisnya ints implisit - ini membutuhkan lebih sedikit kode, dan karenanya lebih efisien. (Dan ya, itu mengkompilasi.)

Cel Skeggs
sumber
8
Bagus. Kesalahpahaman yang disengaja atas pertanyaan :-)
John Dvorak
6
Anda dapat mengoptimalkan ini return a && b;. Lebih pendek, jadi lebih cepat.
Ry-
1
@minitech: Saya memutuskan tidak melakukannya untuk membuat kode sedikit lebih buruk. Jika saya ingin melangkah lebih jauh dengan itu, saya akan berhasil return a&b;.
Cel Skeggs
1
C harus #include<stdbool.h>mendefinisikan truedan false.
leewz
1
Ya, #include<stdbool.h>tampaknya hanya menjadi tiga #defines 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 implisit intuntuk versi "pendek".
leewz
31

Berikut ini skrip shell sederhana untuk melakukannya:

curl "http://www.bing.com/search?q=$1%2A$2&go=&qs=n&form=QBLH&pq=$1%2A$2" -s \
| sed -e "s/[<>]/\n/g" \
| grep "^[0-9 *]*=[0-9 ]*$"

PEMBARUAN: Tentu saja, untuk melakukannya dalam C, cukup bungkus exec("bash", "-c", ...). (Terima kasih, AmeliaBR)

Vroo
sumber
41
Saya tidak bisa memutuskan mana yang lebih buruk. Bahwa Anda melakukan outsourcing perhitungan Anda ke mesin pencari, atau bahwa mesin pencarian yang Anda pilih adalah Bing. Sayangnya, saya tidak berpikir ini akan berhasil untuk OP kita yang malang, yang membutuhkan sesuatu dalam C.
AmeliaBR
5
Terima kasih telah menangkap pengawasan itu. FYI, saya menggunakan Bing karena Google membuatnya lebih rumit untuk mengeluarkan permintaan seperti ini - Anda harus menambahkan header untuk meyakinkan Google bahwa permintaan Anda benar-benar berasal dari browser.
Vroo
2
@abarnert hmm ... apakah Bing mengerti "waktu"? Wolfram Alpha mungkin.
John Dvorak
2
@ JanDvorak: Ya, Wolfram bekerja. (Catat %20untuk 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.
abarnert
3
@JanDvorak: Itu tidak menyenangkan. Saya menantikan seseorang yang menulis perpustakaan OCR sederhana tanpa penambahan atau penggandaan ...
abarnert
27

Mengapa, mari kita lakukan pencarian separuh rekursif antara INT64_MIN dan INT64_MAX!

#include <stdio.h>
#include <stdint.h>

int64_t mul_finder(int32_t a, int32_t b, int64_t low, int64_t high)
{
    int64_t result = (low - (0 - high)) / 2;
    if (result / a == b && result % a == 0)
        return result;
    else
        return result / a < b ?
            mul_finder(a, b, result, high) :
            mul_finder(a, b, low, result);
}

int64_t mul(int32_t a, int32_t b)
{
    return a == 0 ? 0 : mul_finder(a, b, INT64_MIN, INT64_MAX);
}

void main(int argc, char* argv[])
{
    int32_t a, b;
    sscanf(argv[1], "%d", &a);
    sscanf(argv[2], "%d", &b);
    printf("%d * %d = %ld\n", a, b, mul(a, b));
}

PS Itu dengan senang hati akan sigsegv dengan beberapa nilai. ;)

treamur
sumber
18

Sayangnya, ini hanya berfungsi untuk bilangan bulat.

Karena penambahan tidak diizinkan, mari buat operator kenaikan terlebih dahulu:

int plusOne(int arg){
  int onMask = 1;
  int offMask = -1;
  while (arg & onMask){
    onMask <<= 1;
    offMask <<= 1;
  }
  return(arg & offMask | onMask);
}

Selanjutnya, kita harus menangani tandanya. Pertama, temukan bit tanda:

int signBit = -1;
while(signBit << 1) signBit <<=1;

Kemudian ambil tanda dan besarnya setiap argumen. Untuk meniadakan angka dalam komplemen dua, membalikkan semua bit, dan menambahkan satu.

int signA = a & signBit;
if(signA) a = plusOne(-1 ^ a);
int signB = b & signBit;
if(signB) b = plusOne(-1 ^ b);
int signRes = signA ^ signB;

Untuk melipatgandakan dua bilangan bulat positif, kita dapat menggunakan makna geometris perkalian:

// 3x4
//
// ooo
// ooo
// ooo
// ooo

int res = 0;
for(int i = 0; i < a; i = plusOne(i))
  for(int j = 1; j < b; j = plusOne(j))
    res = plusOne(res);

if(signRes) res = plusOne(-1 ^ res);

troll:

  • Penambahan tidak diizinkan, tetapi apakah a++benar - benar dianggap sebagai tambahan? Saya yakin guru itu bermaksud untuk mengizinkannya.
  • Bergantung pada komplemen dua, tetapi itu adalah perilaku yang ditentukan implementasi dan platform target tidak ditentukan.
  • Demikian pula, mengasumsikan pengurangan dan pembagian juga dilarang.
  • << sebenarnya perkalian dengan kekuatan dua, sehingga secara teknis harus dianulir.
  • diagram uneccesary adalah uneccesary. Juga, itu bisa ditransposisikan untuk menyimpan satu baris.
  • pengulangan pengulangan -1bukan cara terbaik untuk menemukan bit tanda. Bahkan jika tidak ada built-in konstan, Anda bisa melakukan pergantian logis kanan -1, lalu membalikkan semua bit.
  • XOR -1 bukan cara terbaik untuk membalikkan semua bit.
  • Seluruh sandiwara dengan representasi tanda-besarnya tidak perlu. Hanya melemparkan ke unsigned dan aritmatika modular akan melakukan sisanya.
  • karena nilai absolut MIN_INT(AKA signBit) negatif, ini rusak untuk nilai itu. Untungnya, ia masih berfungsi dalam setengah kasus, karena MIN_INT * [even number] harus nol.Juga, plusOnebreak for -1, menyebabkan loop tak terbatas kapan saja hasilnya meluap. plusOneberfungsi dengan baik untuk nilai apa pun. Maaf bila membingungkan.
John Dvorak
sumber
+1 untuk troll kode aktual: Sepertinya harus berfungsi, tetapi sangat mungkin akan meledak pada OP dan dia tidak akan tahu mengapa.
Kevin
1
Dimungkinkan untuk melakukan penambahan tanpa operator penambahan APAPUN dengan hanya menggunakan shift, XOR dan AND. Semua ++ ini membuat kepalaku sakit - ADD sedikit dengan carry is (x ^ y) | ((x & y) << 1) (modulo setiap kesalahan yang disebabkan oleh mengetik di kotak teks kecil jelek ini.)
Julie di Austin
@JulieinAustin ya. Algoritma ini bahkan lebih tidak efisien daripada yang seharusnya. Haruskah saya mengubah daftar troll? :-)
John Dvorak
1
@JulieinAustin (x ^ y) | ((x & y) << 1)tidak bekerja, ia tidak akan menyebarkan carry ketika x atau y dan carry keduanya benar di posisi yang sama :)
hobbs
solusi @ hobbs: alih-alih ORing, tambahkan secara rekursif jika carry bukan nol.
John Dvorak
14

Berfungsi untuk nomor floating point:

float mul(float a, float b){
  return std::exp(std::log(a) - std::log(1.0 / b));
}
nbubis
sumber
11

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:

#include <Python.h>

void multiply(int a, int b) {
    PyObject *operator_name, *operator, *mul, *pa, *pb, *args, *result;
    int result;

    operator_name = PyString_FromString("operator");
    operator = PyImport_Import(operator_name);
    Py_DECREF(operator_name);
    mul = PyObject_GetAttrString(operator, "__mul__");
    pa = PyLong_FromLong((long)a);
    pb = PyLong_FromLong((long)b);
    args = PyTuple_New(2);
    PyTuple_SetItem(args, 0, pa);
    PyTuple_SetItem(args, 1, pb);
    presult = PyObject_CallObject(mul, args);
    Py_DECREF(args);
    Py_DECREF(mul);
    Py_DECREF(operator);
    result = (int)PyLong_AsLong(presult);
    Py_DECREF(presult);
    return result;
}

int main(int argc, char *argv[]) {
    int c;
    Py_Initialize();
    c = multiply(2, 3);
    printf("2 * 3 = %d\n", c);
    Py_Finalize();
}
abarnert
sumber
10

Tidak satu pun dari jawaban lain yang secara teoritis masuk akal. Seperti komentar pertama pada pertanyaan mengatakan:

Harap lebih spesifik tentang "angka"

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:

/* The empty set is 0. */
set_t zero() {
    return set_new();
}

/* The successor of n is n U {n}. */
set_t successor(set_t n) {
    set_t result = set_copy(n);
    set_t set_of_n = set_new();
    set_add(set_of_n, n);
    set_union(result, set_of_n);
    set_free(set_of_n);
    return result;
}

/* It is an error to call this on 0, which will be reported by
   running out of memory. */
set_t predecessor(set_t n) {
    set_t pred = zero();
    while (1) {
        set_t next = successor(pred);
        if (set_equal(next, n)) {
            set_free(next);
            return pred;
        }
        set_free(pred);
    }
}        

set_t add(set_t a, set_t b) {
    if (set_empty(b)) {
        /* a + 0 = a */
        return a;
    } else {
        /* a + successor(b) = successor(a+b) */
        set_t pred_b = predecessor(b)
        set_t pred_ab = add(a, pred_b);
        set_t result = successor(pred_ab);
        set_free(pred_b);
        set_free(pred_ab);
        return result;
    }
}

set_t multiply(set_t a, set_t b) {
    if (set_empty(b)) {
        /* a * 0 = 0 */
        return b;
    } else {
        /* a * successor(b) = a + (a * b) */
        set_t pred_b = predecessor(b)
        set_t pred_ab = mul(a, pred_b);
        set_t result = successor(pred_ab);
        set_free(pred_b);
        set_free(pred_ab);
        return result;
    }
}

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?

abarnert
sumber
1
Wow. Anda bahkan lebih lambat dari saya.
John Dvorak
10
unsigned add( unsigned a, unsigned b )
{
    return (unsigned)&((char*)a)[b];  // ignore compiler warnings
       // (if pointers are bigger than unsigned). it still works.
}
unsigned umul( unsigned a, unsigned b )
{
    unsigned res = 0;
    while( a != 0 ){
        if( a & 1) res = add( res, b );
        b <<= 1;
        a >>= 1;
    }
    return res;
}

int mul( int a, int b ){
    return (int)umul( (unsigned)a, (unsigned)b );
}

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.

static unsigned sumtab[17][16]= {
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15},
{ 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16},
{ 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17},
{ 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18},
{ 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19},
{ 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20},
{ 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21},
{ 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22},
{ 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23},
{ 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24},
{10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25},
{11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26},
{12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27},
{13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28},
{14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29},
{15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30},
{16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31}
};

unsigned add( unsigned a, unsigned b )
{
   static const int add4hack[8] =  {4,8,12,16,20,24,28,32};
   unsigned carry = 0;
   unsigned (*sumtab0)[16] = &sumtab[0];
   unsigned (*sumtab1)[16] = &sumtab[1];
   unsigned result = 0;
   int nshift = 0;
   while( (a|b) != 0 ){
      unsigned psum = (carry?sumtab1:sumtab0)[ a & 0xF ][ b & 0xF ];
      result = result | ((psum & 0xF)<<nshift);
      carry = psum >> 4;
      a = a >> 4
      b = b >> 4;
      nshift= add4hack[nshift>>2];  // add 4 to nshift.
   }
   return result;
}
greggo
sumber
Ups, ada *char (walaupun ini bukan multiplikasi)
Sarge Borsch
Eh, pencarian tabel menggunakan tambahan - (a [i]) sama dengan (* (a + i)).
Julie di Austin
@ JulieinAustin saya sebutkan itu. Pencarian tabel dapat dilakukan tanpa menambahkan, dengan menggabungkan bidang (seperti yang diilustrasikan dalam tautan IBM 1620, tetapi berantakan untuk mengaturnya di C - untuk satu hal Anda perlu menyelaraskan tabel ke alamat yang tepat sehingga indeks dapat menjadi baru saja masuk.
greggo
8

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).

#include <math.h>
main()
{
  int a = 6;
  int b = 7;
  return fma(a,b,0);
}
Mark Lakata
sumber
8

Solusi troll saya untuk unsigned int:

#include<stdio.h>

unsigned int add(unsigned int x, unsigned int y)
{
  /* An addition of one bit corresponds to the both following logical operations
     for bit result and carry:
        r     = x xor y xor c_in
        c_out = (x and y) or (x and c_in) or (y and c_in)
     However, since we dealing not with bits but words, we have to loop till
     the carry word is stable
  */
  unsigned int t,c=0;
  do {
    t = c;
    c = (x & y) | (x & c) | (y & c);
    c <<= 1;
  } while (c!=t);
  return x^y^c;
}

unsigned int mult(unsigned int x,unsigned int y)
{
  /* Paper and pencil method for binary positional notation:
     multiply a factor by one (=copy) or zero
     depending on others factor actual digit at position, and  shift 
     through each position; adding up */
  unsigned int r=0;
  while (y != 0) {
    if (y & 1) r = add(r,x);
    y>>=1;
    x<<=1;
  }
  return r;
}

int main(int c, char** param)
{
  unsigned int x,y;
  if (c!=3) {
     printf("Fuck!\n");
     return 1;
  }
  sscanf(param[1],"%ud",&x);
  sscanf(param[2],"%ud",&y);
  printf("%d\n", mult(x,y));
  return 0;
}
Matthias
sumber
1
+1 Implementasi evaluasi carry yang bagus. Saya suka kode Anda :)
yo '
@ BЈовић: Kesalahan saya, saya pikir troll bukan tentang pemahaman. Mengubah nama dan menambahkan komentar.
Matthias
Maaf. Saya salah paham tentang tag itu, dan tentang apa sebenarnya Q itu. Anda harus mengembalikannya
13овић
@Matthias dalam hal ini berguna untuk memahami cara kerjanya sehingga kami dapat menghargai betapa rumitnya operasi konvergen-carry. Dalam situasi kode-troll yang sebenarnya, komentar dapat dihapus :-)
greggo
Saya ingin menunjukkan bahwa jika Anda ingin menambahkan angka sedikit terbalik (dengan tinggi untuk membawa alat peraga) dan Anda tidak memiliki instruksi 'bitrev', ini mungkin merupakan pendekatan yang masuk akal (setelah mengubah ke c> > = 1 tentu saja)
greggo
7

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.

#include <stdio.h>
#include <limits.h>
#include "omp.h"

int mult(int a, int b);

void main(){
        int first;
        int second;
        scanf("%i %i", &first, &second);
        printf("%i x %i = %i\n", first, second, mult(first,second));
}

int mult(int second, int first){
        int answer = INT_MAX;
        omp_set_num_threads(second);
        #pragma omp parallel
        for(second = first; second > 0; second--) answer--;
        return INT_MAX - answer;
}

Berikut ini contoh penggunaannya:

$ ./multiply
5 6
5 x 6 = 30

The #pragma omp paralleldirektif membuat OpenMP membagi setiap bagian dari untuk loop ke unit eksekusi yang berbeda, jadi kita mengalikan secara paralel!

Perhatikan bahwa Anda harus menggunakan -fopenmpflag untuk memberi tahu kompiler untuk menggunakan OpenMP.


Troll bagian:

  1. Menyesatkan tentang penggunaan pemrograman paralel.
  2. Tidak berfungsi pada angka negatif (atau besar).
  3. Tidak benar-benar membagi bagian-bagian dari forloop - setiap thread menjalankan loop.
  4. Nama variabel yang mengganggu dan penggunaan kembali variabel.
  5. Ada kondisi balapan yang halus pada answer--; sebagian besar waktu, itu tidak akan muncul, tetapi kadang-kadang itu akan menyebabkan hasil yang tidak akurat.
milinon
sumber
2
Mengapa tidak menggabungkan ini dengan jawaban SIMD Paul R, sehingga Anda dapat menjalankan 32x lebih cepat daripada 8x? Meskipun benar-benar, Anda ingin melibatkan GPU serta inti; maka itu akan benar - benar menyala. :)
abarnert
2
Mungkin juga menggunakan OpenMPI untuk menjalankannya pada beberapa mesin secara paralel.
milinon
6

Sayangnya, perkalian adalah masalah yang sangat sulit dalam ilmu komputer. Solusi terbaik adalah dengan menggunakan pembagian sebagai gantinya:

#include <stdio.h>
#include <limits.h>
int multiply(int x, int y) {
    int a;
    for (a=INT_MAX; a>1; a--) {
        if (a/x == y) {
            return a;
        }
    }
    for (a=-1; a>INT_MIN; a--) {
        if (a/x == y) {
            return a;
        }
    }
    return 0;
}
main (int argc, char **argv) {
    int a, b;
    if (argc > 1) a = atoi(argv[1]);
    else a = 42;
    if (argc > 2) b = atoi(argv[2]);
    else b = 13;
    printf("%d * %d is %d\n", a, b, multiply(a,b));
}
pengguna3175123
sumber
6

Dalam kehidupan nyata saya biasanya merespons trolling dengan pengetahuan, jadi inilah jawaban yang tidak troll sama sekali. Ini berfungsi untuk semua intnilai sejauh yang saya bisa lihat.

int multiply (int a, int b) {
  int r = 0;
  if (a < 0) { a = -a; b = -b }

  while (a) {
    if (a&1) {
      int x = b;
      do { int y = x&r; r ^= x; x = y<<1 } while (x);
    }
    a>>=1; b<<=1;
  }
  return r;
}

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 jika anegatif (dan tidak, saya menolak untuk menghitung negasi sebagai semacam penambahan atau perkalian). Kemudian while (a)loop menambahkan salinan bergeser bke hasil untuk setiap bit yang diset a. The doLoop mengimplementasikan r += xmenggunakan dan, xor, dan pergeseran dalam apa yang jelas satu set setengah-penambah, dengan membawa bit dimasukkan kembali ke xsampai 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).

hobbs
sumber
4
Si penanya tidak troll. Anda seharusnya troll.
John Dvorak
2
Ini troll sembunyi-sembunyi! Kegagalan rahasia ada pada == INT_MIN.
Jander
1
@ Jander hmm. Ya, itu bagus. Saya menduga (pada sistem komplemen dua biasa) hasil meniadakan masih negatif, dan while(a)loop tidak pernah berakhir.
hobbs
@ hobbs Ya, itu terdengar benar bagi saya. Kalau tidak, jawaban yang sangat cantik.
Jander
6
 int bogomul(int A, int B)
{
    int C = 0;
    while(C/A != B)
    {

        print("Answer isn't: %d", C);
        C = rand();

    }
    return C;
}
Chengarda
sumber
1
Ini akan gagal total jika hasilnya meluap. Bagus! Saya kira Anda tidak harus mencetak.
John Dvorak
2
gagal untuk a = 2, b = 2, c = 5
13овић
@ BЈовић: while(C/A != B || C%A)?
abarnert
2
Perhatikan bahwa ini benar-benar upaya untuk melakukan hal yang sama dengan penerus Deep Thought, tetapi untuk semua kemungkinan alam semesta , bukan hanya di mana jawabannya adalah 42. Yang akan sangat mengesankan jika bukan karena bug. Dan kurangnya penanganan kesalahan dalam kasus Vogons.
abarnert
1
Membutuhkan banyak utas. Anda tahu, untuk membuatnya efisien.
greggo
6

Membuang ini ke dalam campuran:

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

int mul(int a, int b)
{
        asm ("mul %2"
            : "=a" (a)
            : "%0" (a), "r" (b) : "cc"
        );
        return a;
}

int main(int argc, char *argv[])
{
        int a, b;

        a = (argc > 1) ? atoi(argv[1]) : 0;
        b = (argc > 2) ? atoi(argv[2]) : 0;

        return printf("%d x %d = %d\n", a, b, mul(a, b)) < 1;
}

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.

Runium
sumber
2
+ msgstr "tanpa menggunakan operator perkalian dan penambahan". Pelokan aturan yang bagus - ini akan sama sekali tidak berguna bagi penanya :-)
John Dvorak
2
Ini sebenarnya bukan solusi C. Plus, gagal dikompilasi pada ARM9 saya.
abarnert
1
@abarnert: Gagal mengenali pernyataan Anda sebagai argumen yang relevan.
Runium
@Sukminder: Pertanyaannya adalah "Apakah mungkin untuk menulis program C ...?" Inline assembly bukan C. Fakta bahwa beberapa kompiler C juga dapat melakukan inline assembly tidak mengubah itu, lebih dari kenyataan bahwa beberapa kompiler C juga dapat melakukan C ++ atau ObjC membuat C ++ atau ObjC dihitung sebagai kode C.
abarnert
2
@abarnert: Ini adalah kode tertanam yang banyak digunakan dalam program C. Meskipun itu adalah cross-breed satu bisa membantah itu adalah program C . Bahkan OP yang masuk akal akan mengenalinya sebagai kode C. Jelas bukan python, atau?
Runium
5
#include <stdio.h>
#include <stdlib.h>

int mult (int n1, int n2);
int add (int n1, int n2 );
int main (int argc, char** argv)
{
        int a,b;
        a = atoi(argv[1]);
        b = atoi(argv[2]);

        printf ("\n%i times %i is %i\n",a,b,mult(a,b));
        return 0;
}

int add (int n1, int n2 )
{
        return n1 - -n2;
}

int mult (int n1, int n2)
{
        int sum = 0;
        char s1='p', s2='p';
        if ( n1 == 0 || n2 == 0 ) return 0;
        if( n1 < 0 )
        {
                s1 = 'n';
                n1 = -n1;
        }
        if( n2 < 0 )
        {
                s2 = 'n';
                n2 = -n2;
        }
        for (int i = 1; i <= n2; i = add( i, 1 ))
        {
                sum = add(sum,  n1);
        }
        if ( s1 != s2 ) sum = -sum;
        return sum;
}
jaybers
sumber
5

Apakah mungkin untuk menulis program C yang mengalikan dua angka tanpa menggunakan operator perkalian dan penambahan?

Tentu:

void multiply() {
    printf("6 times 7 is 42\n");
}

Tapi tentu saja itu curang; jelas dia ingin bisa menyediakan dua nomor, bukan?

void multiply(int a, int b) {
    int answer = 42;
    if (answer / b != a || answer % b) {
        printf("The answer is 42, so that's the wrong question.\n");
    } else {
        printf("The answer is 42, but that's probably not the right question anyway.\n");
    }
}
abarnert
sumber
Kenapa, sama sekali tidak jelas bagiku!
leewz
4

Tidak ada aritmatika seperti aritmatika pointer:

int f(int a, int b) {
        char x[1][b];
        return x[a] - x[0];
}

int
main(int ac, char **av) {
        printf("%d\n", f(atoi(av[1]),atoi(av[2])));
        return 0;
}

Fungsi ini fmenerapkan multiplikasi. maincukup menyebutnya dengan dua argumen.
Berfungsi untuk angka negatif juga.

ugoren
sumber
Negatif a, ya, negatif bsaya rasa tidak. Tapi itu bisa diperbaiki dengan banyak cara kreatif. Paling sederhana adalah sign_a ^ = sign_b, sign_b = 0.
MSalters
@MSalters, diuji dan berfungsi untuk semua kombinasi tanda (dengan Linux / gcc).
ugoren
3

C #

Saya pikir pengurangan dan negasi tidak diperbolehkan ... Pokoknya:

int mul(int a, int b)
{
    int t = 0;
    for (int i = b; i >= 1; i--) t -= -a;
    return t;
}
thepirat000
sumber
1
Ini adalah solusi tepat yang saya pikirkan ... tetapi datang ke pesta terlambat saya tahu itu masalah menggulir ke bawah sampai saya menemukan bahwa seseorang sudah menulisnya. Namun, Anda mendapatkan - (- 1) dari saya.
Floris
3

C dengan SSE intrinsics (karena semuanya lebih baik dengan SIMD):

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

static float mul(float a, float b)
{
    float c;

    __m128 va = _mm_set1_ps(a);
    __m128 vb = _mm_set1_ps(b);
    __m128 vc = _mm_mul_ps(va, vb);
    _mm_store_ss(&c, vc);
    return c;
}

int main(int argc, char *argv[])
{
    if (argc > 2)
    {
        float a = atof(argv[1]);
        float b = atof(argv[2]);
        float c = mul(a, b);
        printf("%g * %g = %g\n", a, b, c);
    }
    return 0;
}

Keuntungan besar dari implementasi ini adalah bahwa ia dapat dengan mudah diadaptasi untuk melakukan 4 perkalian paralel tanpa *atau +jika diperlukan.

Paul R
sumber
Saya tidak berpikir ini trolling ...
John Dvorak
Benarkah ? Saya pikir penggunaan SIMD yang sia-sia, serampangan, dan spesifik arsitektur akan memenuhi syarat untuk kode-trolling?
Paul R
hmm ... benar. Tidak menyadari bahwa ini khusus arsitektur.
John Dvorak
3
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define INF 1000000

char cg[INF];

int main()
{
    int a, b;

    char bg[INF];
    memset(bg, '*', INF);

    scanf("%d%d", &a, &b);

    bg[b] = 0;

    while(a--)  
        strcat(cg, bg);

    int result;
    printf("%s%n",cg,&result);
    printf("%d\n", result);

    return 0;
}
  • hanya bekerja untuk hasil perkalian <1.000
  • Sejauh ini tidak dapat dihilangkan - operator, mungkin ditingkatkan di sini
  • menggunakan specifier format% n di printf untuk menghitung jumlah karakter yang dicetak (Saya memposting ini terutama untuk mengingatkan keberadaan% n di C, bukannya% n tentu saja bisa macet dll)
  • Mencetak a * b karakter '*'
marol
sumber
Sekarang menunggu solusi 'emulasi mesin turing'.
greggo
1
sedangkan strlen(cg) != aadalah metode yang sangat trolling untuk menghilangkan --(membuatnya O (N * N)).
MSalters
3

Mungkin terlalu cepat :-(

   unsigned int add(unsigned int a, unsigned int b)
    {
        unsigned int carry;

        for (; b != 0; b = carry << 1) {
            carry = a & b;
            a ^= b;
        }
        return a;
    }

    unsigned int mul(unsigned int a, unsigned int b)
    {
        unsigned int prod = 0;

        for (; b != 0;  a <<= 1, b >>= 1) {
            if (b & 1)
                prod = add(prod, a);
        }
        return prod;
    }
David Laight
sumber
1
Ungh. Ini bukan trolling. Ini adalah cara yang sepenuhnya masuk akal untuk melakukan ini.
John Dvorak
1
Ini trolly karena terlalu cepat :-)
Timtech
3

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.

mult n m = length . concat . replicate n . replicate m $ '|'
mhwombat
sumber
3
int multiply(int a, int b) {
    return sizeof(char[a][b]);
}

Ini dapat bekerja di C99, jika cuaca tepat, dan kompiler Anda mendukung omong kosong yang tidak ditentukan.

Konrad Borowski
sumber
3

Karena OP tidak meminta C , inilah salah satu dari (Oracle) SQL!

WITH
   aa AS (
      SELECT LEVEL AS lvl 
      FROM dual
      CONNECT BY LEVEL <= &a
   ),
   bb AS (
      SELECT LEVEL AS lvl
      FROM dual
      CONNECT BY LEVEL <= &b
   )
SELECT COUNT(*) AS addition
FROM (SELECT * FROM aa UNION ALL SELECT * FROM bb);

WITH
   aa AS (
      SELECT LEVEL AS lvl 
      FROM dual
      CONNECT BY LEVEL <= &a
   ),
   bb AS (
      SELECT LEVEL AS lvl
      FROM dual
      CONNECT BY LEVEL <= &b
   )
SELECT COUNT(*) AS multiplication
FROM aa CROSS JOIN bb;
SQB
sumber
1
Ya Tuhan, penuh dengan *s!
Paul R
1
@ PaulR :) tapi mereka bukan operator .
SQB
2
int add(int a, int b) {
    return 0 - ((0 - a) - b);
}

int mul(int a, int b) {
    int m = 0;
    for (int count = b; count > 0; m = add(m, a), count = add(count, 0 - 1)) { }
    return m;
}

Dapat mengandung jejak UD.

Joker_vD
sumber
2
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
  int x = atoi(argv[1]);
  int y = atoi(argv[2]);
  FILE *f = fopen("m","wb");
  char *b = calloc(x, y);
  if (!f || !b || fwrite(b, x, y, f) != y) {
    puts("503 multiplication service is down for maintenance");
    return EXIT_FAILURE;
  }
  printf("%ld\n", ftell(f));
  fclose(f);
  remove("m");
  return 0;
}

Uji coba:

$ ./a.out 1 0
0
$ ./a.out 1 1
1
$ ./a.out 2 2
4
$ ./a.out 3 2
6
$ ./a.out 12 12
144
$ ./a.out 1234 1234
1522756
Kaz
sumber