teratail
回答率
85.48%
質問するログイン新規登録
トップCに関する質問算術演算子を使わずに乗算する方法

編集履歴

回答編集履歴

3

add_rが単純末尾再帰になっとらんかったのを修正

2018/11/04 02:41

投稿

raccy
raccy

スコア21735

test CHANGED
@@ -92,7 +92,7 @@
92
92
 
93
93
  assert(b > 0);
94
94
 
95
- return add(++a, --b);
95
+ return add_r(++a, --b);
96
96
 
97
97
  }
98
98
 

2

スタックオーバーフローなど不要、そう、tertailがあればね

2018/11/04 02:41

投稿

raccy
raccy

スコア21735

test CHANGED
@@ -202,4 +202,4 @@
202
202
 
203
203
 
204
204
 
205
- `div()`は、0除算でエラーにならない事を除き、標準の`/`と動作を合わせたつもりです、たぶん。**速度は全く考慮に入れていません。**`assert()`を有効にしたい場合は`#define NDEBUG`をコメントアウトしてください。ビット演算子やシフト演算子の実装については力尽きましたので、誰かがやってくれることでしょう。
205
+ `div()`は、0除算でエラーにならない事を除き、標準の`/`と動作を合わせたつもりです、たぶん。**速度は全く考慮に入れていません。**インクリメントのオーバーフローやデクリメントのアンダーフローは考慮していませんが、末尾再帰になっていますので、適当に最適化オプションを付けていればスタックオーバーフローは起きないはずです。`assert()`を有効にしたい場合は`#define NDEBUG`をコメントアウトしてください。ビット演算子やシフト演算子の実装については力尽きましたので、誰かがやってくれることでしょう。

1

ソースコード変更

2018/11/04 02:38

投稿

raccy
raccy

スコア21735

test CHANGED
@@ -1,20 +1,100 @@
1
- インクリメントとデクリメントだけで四則演算を全て実装してみました。
1
+ インクリメントとデクリメントだけで四則演算を全て実装してみました。算術演算子禁止として、[Arithmetic operators - cppreference.com](https://en.cppreference.com/w/c/language/operator_arithmetic)にある全ての演算子を使用しないようにしました。また、`while`や`for`および`goto`を用いたループも禁止しました。
2
2
 
3
3
 
4
4
 
5
5
  ```C
6
6
 
7
+ /**
8
+
9
+ * Implementation of arithmetic operators without using arithmetic operators.
10
+
11
+ * https://en.cppreference.com/w/c/language/operator_arithmetic
12
+
13
+ */
14
+
15
+
16
+
17
+ #define NDEBUG
18
+
19
+ #include <assert.h>
20
+
7
21
  #include <stdio.h>
8
22
 
9
23
 
10
24
 
25
+ int plu(int a); // +a
26
+
27
+ int min(int a); // -a
28
+
29
+ int add(int a, int b); // a + b
30
+
31
+ int sub(int a, int b); // a - b
32
+
33
+ int pro(int a, int b); // a * b
34
+
35
+ int div(int a, int b); // a / b
36
+
37
+ int mod(int a, int b); // a % b
38
+
39
+
40
+
11
- int add(int a, int b);
41
+ int plu(int a) { return a; }
12
-
42
+
43
+
44
+
13
- int sub(int a, int b);
45
+ static inline int min_inc_r(int a, int b)
46
+
14
-
47
+ {
48
+
49
+ if (a == 0) return b;
50
+
51
+ assert(a < 0);
52
+
53
+ return min_inc_r(++a, ++b);
54
+
55
+ }
56
+
57
+
58
+
59
+ static inline int min_dec_r(int a, int b)
60
+
61
+ {
62
+
63
+ if (a == 0) return b;
64
+
65
+ assert(a > 0);
66
+
67
+ return min_dec_r(--a, --b);
68
+
69
+ }
70
+
71
+
72
+
15
- int mul(int a, int b);
73
+ int min(int a)
74
+
16
-
75
+ {
76
+
77
+ if (a == 0) return 0;
78
+
79
+ if (a < 0) return min_inc_r(a, 0);
80
+
81
+ return min_dec_r(a, 0);
82
+
83
+ }
84
+
85
+
86
+
17
- int div(int a, int b);
87
+ static inline int add_r(int a, int b)
88
+
89
+ {
90
+
91
+ if (b == 0) return a;
92
+
93
+ assert(b > 0);
94
+
95
+ return add(++a, --b);
96
+
97
+ }
18
98
 
19
99
 
20
100
 
@@ -22,35 +102,57 @@
22
102
 
23
103
  {
24
104
 
25
- if (b == 0) return a;
26
-
27
- if (b < 0) return -add(-a, -b);
105
+ if (b < 0) return min(add(min(a), min(b)));
28
-
106
+
29
- return add(++a, --b);
107
+ return add_r(a, b);
30
-
108
+
31
- }
109
+ }
32
-
33
-
34
-
110
+
111
+
112
+
35
- int sub(int a, int b)
113
+ int sub(int a, int b) { return add(a, min(b)); }
114
+
115
+
116
+
36
-
117
+ static inline int pro_r(int a, int b, int r)
118
+
37
- {
119
+ {
120
+
38
-
121
+ if (b == 0) return r;
122
+
123
+ assert(b > 0);
124
+
39
- return add(a, -b);
125
+ return pro_r(a, --b, add(r, a));
40
-
126
+
41
- }
127
+ }
42
-
43
-
44
-
128
+
129
+
130
+
45
- int mul(int a, int b)
131
+ int pro(int a, int b)
46
-
132
+
47
- {
133
+ {
48
-
134
+
49
- if (b == 0) return 0;
135
+ if (b == 0) return 0;
136
+
50
-
137
+ if (b < 0) return pro(min(a), min(b));
138
+
139
+ return pro_r(a, b, 0);
140
+
141
+ }
142
+
143
+
144
+
145
+ static inline int div_r(int a, int b, int r)
146
+
147
+ {
148
+
149
+ assert(b > 0);
150
+
151
+ if (a == 0) return r;
152
+
51
- if (b < 0) return mul(-a, -b);
153
+ if (a < 0) return --r;
52
-
154
+
53
- return add(mul(a, --b), a);
155
+ return div_r(sub(a, b), b, ++r);
54
156
 
55
157
  }
56
158
 
@@ -60,17 +162,19 @@
60
162
 
61
163
  {
62
164
 
63
- if (b == 0) return 0; // or error
165
+ if (b == 0) return 0; // or error
64
-
166
+
65
- if (b < 0) return div(-a, -b);
167
+ if (b < 0) return min(div(a, min(b)));
66
-
168
+
67
- if (a < 0) return -div(-a, b);
169
+ if (a < 0) return min(div(min(a), b));
68
-
69
- if (a < b) return 0;
170
+
70
-
71
- return add(div(a - b, b), 1);
171
+ return div_r(a, b, 0);
72
-
172
+
73
- }
173
+ }
174
+
175
+
176
+
177
+ int mod(int a, int b) { return sub(a, pro(div(a, b), b)); }
74
178
 
75
179
 
76
180
 
@@ -78,13 +182,19 @@
78
182
 
79
183
  {
80
184
 
185
+ printf("+42 = %d\n", plu(42));
186
+
187
+ printf("-42 = %d\n", min(42));
188
+
81
- printf("%d\n", add(6, 7));
189
+ printf("7 + 6 = %d\n", add(7, 6));
82
-
190
+
83
- printf("%d\n", sub(6, 7));
191
+ printf("7 - 6 = %d\n", sub(7, 6));
192
+
84
-
193
+ printf("7 * 6 = %d\n", pro(7, 6));
194
+
195
+ printf("7 / 6 = %d\n", div(7, 6));
196
+
85
- printf("%d\n", mul(6, 7));
197
+ printf("7 %% 6 = %d\n", mod(7, 6));
86
-
87
- printf("%d\n", div(6, 7));
88
198
 
89
199
  }
90
200
 
@@ -92,4 +202,4 @@
92
202
 
93
203
 
94
204
 
95
- `div()`は標準の`div()`と動作を合わせたつもりです、たぶん。**速度は全く考慮に入れていません。**`mul()`と`div()`の再帰部分は最適化されないみたいですので、**数が大きいとスタックオーバーフローで落ちます。**末尾再帰になるように`mul()`と`div()`を書き直せば落ちないようにはできるはずです。
205
+ `div()`は、0除算でエラーにならない事を除き、標準の`/`と動作を合わせたつもりです、たぶん。**速度は全く考慮に入れていません。**`assert()`を有効にしたい場合は`#define NDEBUG`をコメントアウトしてください。ビット演算子やシフト演算子の実装については力尽きましたので、誰かがやってくれることでしょう。