回答編集履歴
3
コメントに対する回答を追加
test
CHANGED
|
@@ -181,3 +181,65 @@
|
|
|
181
181
|
nより小さい、すなわち 0より小さい 2のべき乗は存在しません。なぜ、問題に
|
|
182
182
|
|
|
183
183
|
「非負整数値 n (0 ≦ n ＜ 2の31乗)」と書かれているのか不思議です。
|
|
184
|
+
|
|
185
|
+
|
|
186
|
+
|
|
187
|
+
**追記3**
|
|
188
|
+
|
|
189
|
+
> ※問題文に、『必要最小限の桁数で1行として』とありますが、こう指定されているということは通常、複数桁で計算結果がでるのでしょうか。ここの意味が調べてもわからなかったのですがどんな意味なのでしょうか。
|
|
190
|
+
|
|
191
|
+
|
|
192
|
+
|
|
193
|
+
2の31乗は 2147483648。
|
|
194
|
+
|
|
195
|
+
入力 n はこれより小さいから n = 2147483647 の時に、
|
|
196
|
+
|
|
197
|
+
これより小さい最大の 2のべき乗は 2の30乗で 1073741824。
|
|
198
|
+
|
|
199
|
+
したがって、標準出力に書き出す値は10桁以下となります。
|
|
200
|
+
|
|
201
|
+
コードを書く人がこれを意識して
|
|
202
|
+
|
|
203
|
+
`printf("%10d\n", n);` や `printf("%010d\n", n);` と書くかもしれません。
|
|
204
|
+
|
|
205
|
+
「必要最小限の桁数」と指定することで `printf("%d\n", n);` と書いてもらう
|
|
206
|
+
|
|
207
|
+
ことを期待しているのではないでしょうか？
|
|
208
|
+
|
|
209
|
+
また、`printf("%d", n);` と書いてしまう人がよくいます。
|
|
210
|
+
|
|
211
|
+
改行コードを出さないので行が完成していません。
|
|
212
|
+
|
|
213
|
+
これを防ぐために「1行」と指定しているのではないかと、私は思っています。
|
|
214
|
+
|
|
215
|
+
|
|
216
|
+
|
|
217
|
+
> ※見比べてここにたどり着く為に、一番最初にnと計算結果をビット表現にするのでしょうか。
|
|
218
|
+
|
|
219
|
+
|
|
220
|
+
|
|
221
|
+
ビット表現にするというより、ビット表現で考えることによって 2のべき乗の
|
|
222
|
+
|
|
223
|
+
意味がよく分かるということです。
|
|
224
|
+
|
|
225
|
+
|
|
226
|
+
|
|
227
|
+
> この0にならないうちは、とは今回の4のように0000になるまで繰り返すという意味でしょうか。
|
|
228
|
+
|
|
229
|
+
|
|
230
|
+
|
|
231
|
+
5、6、7 は (n & n-1) が 0 ではないので、n &= n-1; で最下位の 1 を消して
|
|
232
|
+
|
|
233
|
+
(n & n-1) が 0 になるまで n & n-1; を繰り返すということです。
|
|
234
|
+
|
|
235
|
+
4 は (n & n-1) が 0 なので、n &= n-1; は実行しません。
|
|
236
|
+
|
|
237
|
+
|
|
238
|
+
|
|
239
|
+
> while文はtrueのうちは繰り返す文なので、この文はn &= -1になるまで（n & n-1）を繰り返す、という意味になる。
|
|
240
|
+
|
|
241
|
+
|
|
242
|
+
|
|
243
|
+
while文は、「while (式) 文」という構文で、「式」の値が 0 でない間「文」を
|
|
244
|
+
|
|
245
|
+
実行します。(n & n-1) が 0 になるまで、n &= n-1; を繰り返します。
|
2
ループ回数 5回のコードを追加
test
CHANGED
|
@@ -139,3 +139,45 @@
|
|
|
139
139
|
while文は分かりませんか？
|
|
140
140
|
|
|
141
141
|
& や &= という演算子が分かりませんか？
|
|
142
|
+
|
|
143
|
+
|
|
144
|
+
|
|
145
|
+
**追記2**
|
|
146
|
+
|
|
147
|
+
`while (n & n-1) n &= n-1;` は、(1の個数 - 1)回ループを回るので、
|
|
148
|
+
|
|
149
|
+
1 の個数が少ないときはいいけれど、1の個数が多いときは時間がかかります。
|
|
150
|
+
|
|
151
|
+
|
|
152
|
+
|
|
153
|
+
ということで、ループ回数がいつも 5回となるコードを書いてみました。
|
|
154
|
+
|
|
155
|
+
```C
|
|
156
|
+
|
|
157
|
+
#include <stdio.h>
|
|
158
|
+
|
|
159
|
+
|
|
160
|
+
|
|
161
|
+
int main(void)
|
|
162
|
+
|
|
163
|
+
{
|
|
164
|
+
|
|
165
|
+
int n, m = 1, k = 32;
|
|
166
|
+
|
|
167
|
+
scanf("%d", &n);
|
|
168
|
+
|
|
169
|
+
while (k >>= 1) (n >> k) && (m <<= k, n >>= k);
|
|
170
|
+
|
|
171
|
+
printf("%d\n", m);
|
|
172
|
+
|
|
173
|
+
}
|
|
174
|
+
|
|
175
|
+
```
|
|
176
|
+
|
|
177
|
+
ただし、n が 0 のときは、m が 1 になるので、それが嫌ならその場合だけ特別
|
|
178
|
+
|
|
179
|
+
扱いする必要があります。とはいうものの、2のべき乗は正の数しかないので、
|
|
180
|
+
|
|
181
|
+
nより小さい、すなわち 0より小さい 2のべき乗は存在しません。なぜ、問題に
|
|
182
|
+
|
|
183
|
+
「非負整数値 n (0 ≦ n ＜ 2の31乗)」と書かれているのか不思議です。
|
1
説明の追加
test
CHANGED
|
@@ -21,3 +21,121 @@
|
|
|
21
21
|
```
|
|
22
22
|
|
|
23
23
|
解説がほしければコメントください。
|
|
24
|
+
|
|
25
|
+
|
|
26
|
+
|
|
27
|
+
**追記**
|
|
28
|
+
|
|
29
|
+
> 質問の方法が間違っていたらすみません。
|
|
30
|
+
|
|
31
|
+
|
|
32
|
+
|
|
33
|
+
タイトルが長すぎます。それは本文中に書くべきことです。
|
|
34
|
+
|
|
35
|
+
タイトルは「2のべき乗に関する問題」とでもすればよいでしょう。
|
|
36
|
+
|
|
37
|
+
|
|
38
|
+
|
|
39
|
+
提示されたコードはコンパイルできません。
|
|
40
|
+
|
|
41
|
+
自分で修正できるところは修正し、
|
|
42
|
+
|
|
43
|
+
それでもエラーになるときは、エラーメッセージを付けてください。
|
|
44
|
+
|
|
45
|
+
|
|
46
|
+
|
|
47
|
+
> 掲題の問を解く場合の考え方について質問させてください。
|
|
48
|
+
|
|
49
|
+
|
|
50
|
+
|
|
51
|
+
問題の意味は理解していますか？
|
|
52
|
+
|
|
53
|
+
具体的に n が 0～9 の時に何を書き出すべきか分かっていますか？
|
|
54
|
+
|
|
55
|
+
分かっているなら、自分はこのように考えた、などと書いてください。
|
|
56
|
+
|
|
57
|
+
|
|
58
|
+
|
|
59
|
+
2のべき乗というのは、1、2、4、8、16、... だというのは分かっていますか？
|
|
60
|
+
|
|
61
|
+
2の 0乗は 1、2の 1乗は 2、 2の 2乗は 4。n が
|
|
62
|
+
|
|
63
|
+
1、2、3、4、5、6、7、8、9 のとき、計算結果は
|
|
64
|
+
|
|
65
|
+
1、2、2、4、4、4、4、8、8。
|
|
66
|
+
|
|
67
|
+
|
|
68
|
+
|
|
69
|
+
n が与えられたとき、n は 1 より大きいか、2より大きいか、4より大きいか
|
|
70
|
+
|
|
71
|
+
と繰り返し、あるところで n が 2のべき乗より小さくなります。
|
|
72
|
+
|
|
73
|
+
その 2のべき乗のひとつ前が求める値です。
|
|
74
|
+
|
|
75
|
+
|
|
76
|
+
|
|
77
|
+
> 現段階では初歩の初歩、for文やif文を学んでいるのですが、この問題をどの関数を使って、解いたら良いかがわからず、
|
|
78
|
+
|
|
79
|
+
|
|
80
|
+
|
|
81
|
+
使う関数は、n の入力と結果の表示です。
|
|
82
|
+
|
|
83
|
+
scanf と printf でよいでしょう。
|
|
84
|
+
|
|
85
|
+
|
|
86
|
+
|
|
87
|
+
質問のコードを見ると
|
|
88
|
+
|
|
89
|
+
printf の使い方がよくわかっていない。
|
|
90
|
+
|
|
91
|
+
if文の使い方がよくわかっていない。
|
|
92
|
+
|
|
93
|
+
for文も、その中の文をどのように書くのかが分かっていない。
|
|
94
|
+
|
|
95
|
+
i を変化させながらその値を利用していない。
|
|
96
|
+
|
|
97
|
+
|
|
98
|
+
|
|
99
|
+
さて、私が書いた `while (n & n-1) n &= n-1;` について説明します。
|
|
100
|
+
|
|
101
|
+
|
|
102
|
+
|
|
103
|
+
2 のべき乗を 2進数で書くと、1、2、4、8 が 0001、0010、0100、1000 となり
|
|
104
|
+
|
|
105
|
+
ビット表現の中に 1 が一つだけしかないことが分かります。
|
|
106
|
+
|
|
107
|
+
|
|
108
|
+
|
|
109
|
+
n が 4、5、6、7 のとき、その 2進表現は、0100、0101、0110、0111 です。
|
|
110
|
+
|
|
111
|
+
これらをすべて 4 の 0100 にしたいということは、最上位の 1以外をすべて
|
|
112
|
+
|
|
113
|
+
0 にすればよいのです。
|
|
114
|
+
|
|
115
|
+
|
|
116
|
+
|
|
117
|
+
n が 4、5、6、7 のとき、n-1 は、0011、0100、0101、0110。
|
|
118
|
+
|
|
119
|
+
&演算子でビット単位のANDをとると、0000、0100、0100、0110。
|
|
120
|
+
|
|
121
|
+
もとのビット表現の最下位の 1 が消えています。
|
|
122
|
+
|
|
123
|
+
|
|
124
|
+
|
|
125
|
+
4 は元から 1 が一つしかなかったので 0000 になっています。
|
|
126
|
+
|
|
127
|
+
5 と 6 は 4 に、7 は 6 になりました。
|
|
128
|
+
|
|
129
|
+
|
|
130
|
+
|
|
131
|
+
このように n & n-1 を繰り返して 0 になる直前が求める値となります。
|
|
132
|
+
|
|
133
|
+
n & n-1 が 0 にならないうちは n &= n-1; を繰り返せばよいので、
|
|
134
|
+
|
|
135
|
+
`while (n & n-1) n &= n-1;` となります。
|
|
136
|
+
|
|
137
|
+
|
|
138
|
+
|
|
139
|
+
while文は分かりませんか？
|
|
140
|
+
|
|
141
|
+
& や &= という演算子が分かりませんか？
|