Q&A
これ、問題が間違っていませんか？
2 のべき乗は、1、2、4、8、16、... で、必ず正の値になります。
n = 0 のとき、2 のべき乗で 0以下のものは存在しません。
初めまして。
掲題の問を解く場合の考え方について質問させてください。
問: 標準入力から非負整数値 n（ 0 ≦ n ＜ 2の31乗 ）を読み取り、n 以下の最大の2のべき乗を計算してその値を必要最小限の桁数で1行として標準出力に書き出すプログラム
現段階では初歩の初歩、for文やif文を学んでいるのですが、この問題をどの関数を使って、解いたら良いかがわからず、アドバイスいただきたいです。
質問の方法が間違っていたらすみません。
よろしくお願いいたします。
#include <stdio.h> int main() { int n,m=0 ; if(scanf("%d",&n)); for(int i=1; n!=0; i++,n>>=1) printf("%d\n"); }
数学的にはよくわからないけど、
2^-∞ は０にならないって事なんですかね・・・
ならないなら間違っているかもしれない(^^;
回答7件
0
まずは標準入力から数値を読み取り、それを標準出力に書き出すだけのコードを組んでみましょう。
まずはそれからです
投稿2020/10/06 13:01
総合スコア87784
0
ベストアンサー
C
1#include <stdio.h> 2 3int main(void) 4{ 5 int n; 6 scanf("%d", &n); 7 while (n & n-1) n &= n-1; 8 printf("%d\n", n); 9}
解説がほしければコメントください。
追記
質問の方法が間違っていたらすみません。
タイトルが長すぎます。それは本文中に書くべきことです。
タイトルは「2のべき乗に関する問題」とでもすればよいでしょう。
提示されたコードはコンパイルできません。
自分で修正できるところは修正し、
それでもエラーになるときは、エラーメッセージを付けてください。
掲題の問を解く場合の考え方について質問させてください。
問題の意味は理解していますか？
具体的に n が 0～9 の時に何を書き出すべきか分かっていますか？
分かっているなら、自分はこのように考えた、などと書いてください。
2のべき乗というのは、1、2、4、8、16、... だというのは分かっていますか？
2の 0乗は 1、2の 1乗は 2、 2の 2乗は 4。n が
1、2、3、4、5、6、7、8、9 のとき、計算結果は
1、2、2、4、4、4、4、8、8。
n が与えられたとき、n は 1 より大きいか、2より大きいか、4より大きいか
と繰り返し、あるところで n が 2のべき乗より小さくなります。
その 2のべき乗のひとつ前が求める値です。
現段階では初歩の初歩、for文やif文を学んでいるのですが、この問題をどの関数を使って、解いたら良いかがわからず、
使う関数は、n の入力と結果の表示です。
scanf と printf でよいでしょう。
質問のコードを見ると
printf の使い方がよくわかっていない。
if文の使い方がよくわかっていない。
for文も、その中の文をどのように書くのかが分かっていない。
i を変化させながらその値を利用していない。
さて、私が書いた while (n & n-1) n &= n-1; について説明します。
2 のべき乗を 2進数で書くと、1、2、4、8 が 0001、0010、0100、1000 となり
ビット表現の中に 1 が一つだけしかないことが分かります。
n が 4、5、6、7 のとき、その 2進表現は、0100、0101、0110、0111 です。
これらをすべて 4 の 0100 にしたいということは、最上位の 1以外をすべて
0 にすればよいのです。
n が 4、5、6、7 のとき、n-1 は、0011、0100、0101、0110。
&演算子でビット単位のANDをとると、0000、0100、0100、0110。
もとのビット表現の最下位の 1 が消えています。
4 は元から 1 が一つしかなかったので 0000 になっています。
5 と 6 は 4 に、7 は 6 になりました。
このように n & n-1 を繰り返して 0 になる直前が求める値となります。
n & n-1 が 0 にならないうちは n &= n-1; を繰り返せばよいので、
while (n & n-1) n &= n-1; となります。
while文は分かりませんか？
& や &= という演算子が分かりませんか？
追記2
while (n & n-1) n &= n-1; は、(1の個数 - 1)回ループを回るので、
1 の個数が少ないときはいいけれど、1の個数が多いときは時間がかかります。
ということで、ループ回数がいつも 5回となるコードを書いてみました。
C
1#include <stdio.h> 2 3int main(void) 4{ 5 int n, m = 1, k = 32; 6 scanf("%d", &n); 7 while (k >>= 1) (n >> k) && (m <<= k, n >>= k); 8 printf("%d\n", m); 9}
ただし、n が 0 のときは、m が 1 になるので、それが嫌ならその場合だけ特別
扱いする必要があります。とはいうものの、2のべき乗は正の数しかないので、
nより小さい、すなわち 0より小さい 2のべき乗は存在しません。なぜ、問題に
「非負整数値 n (0 ≦ n ＜ 2の31乗)」と書かれているのか不思議です。
追記3
※問題文に、『必要最小限の桁数で1行として』とありますが、こう指定されているということは通常、複数桁で計算結果がでるのでしょうか。ここの意味が調べてもわからなかったのですがどんな意味なのでしょうか。
2の31乗は 2147483648。
入力 n はこれより小さいから n = 2147483647 の時に、
これより小さい最大の 2のべき乗は 2の30乗で 1073741824。
したがって、標準出力に書き出す値は10桁以下となります。
コードを書く人がこれを意識して
printf("%10d\n", n); や printf("%010d\n", n); と書くかもしれません。
「必要最小限の桁数」と指定することで printf("%d\n", n); と書いてもらう
ことを期待しているのではないでしょうか？
また、printf("%d", n); と書いてしまう人がよくいます。
改行コードを出さないので行が完成していません。
これを防ぐために「1行」と指定しているのではないかと、私は思っています。
※見比べてここにたどり着く為に、一番最初にnと計算結果をビット表現にするのでしょうか。
ビット表現にするというより、ビット表現で考えることによって 2のべき乗の
意味がよく分かるということです。
この0にならないうちは、とは今回の4のように0000になるまで繰り返すという意味でしょうか。
5、6、7 は (n & n-1) が 0 ではないので、n &= n-1; で最下位の 1 を消して
(n & n-1) が 0 になるまで n & n-1; を繰り返すということです。
4 は (n & n-1) が 0 なので、n &= n-1; は実行しません。
while文はtrueのうちは繰り返す文なので、この文はn &= -1になるまで（n & n-1）を繰り返す、という意味になる。
while文は、「while (式) 文」という構文で、「式」の値が 0 でない間「文」を
実行します。(n & n-1) が 0 になるまで、n &= n-1; を繰り返します。
投稿2020/10/06 15:31
編集2020/10/09 20:10総合スコア8224
ご回答ありがとうございます。
もし宜しければ解説いただけませんでしょうか。宜しくお願い致します。
ありがとうございます。いただいたコメントを一つ一つ読ませていただいております。取り急ぎ御礼申し上げます。
まず、質問のタイトルについて修正致しました。ご指摘有難うございます。
下記は頂いたご回答に基づいて考え、自分の理解した部分と理解が難しかったところなのですが、見ていただけませんでしょうか。
■問題の意味は理解していますか？
整数n（0以上2の31乗未満）を読み取り、整数nを超えるひとつ手前の2のべき乗を求める、と理解しました。※問題文に、『必要最小限の桁数で1行として』とありますが、こう指定されているということは通常、複数桁で計算結果がでるのでしょうか。ここの意味が調べてもわからなかったのですがどんな意味なのでしょうか。
■具体的に n が 0～9 の時に何を書き出すべきか分かっていますか？
nに0〜9を読み取り、それぞれの数値以下の2のべき乗のうち最大値を求める。
1、2、3、4、5、6、7、8、9 のとき、計算結果は
1、2、2、4、4、4、4、8、8。
while (n & n-1) n &= n-1; について
■n が 4、5、6、7 のとき、0100、0101、0110、0111 、これらをすべて 4 の 0100 にしたい。最上位の 1以外をすべて0 にすればよい
ここは、nが4、5、6、7の場合の計算結果が全て4なので0100にしたく、その為には5、6、7の最上位以外の1を0にすれば良いことはわかりました。※見比べてここにたどり着く為に、一番最初にnと計算結果をビット表現にするのでしょうか。
■n が 4、5、6、7 のとき、n-1 は、0011、0100、0101、0110。
ここでも上記の事実に気がつく為にはビット表現にして見比べる必要があるということでしょうか
■&演算子でビット単位のANDをとると、0000、0100、0100、0110。
＆演算子は2つを見比べて両方1の時だけ１、それ以外は0を返すので、
例えば整数5は2進数で0101、n-1は0100＆演算子を使えば4の0100になる。
これをn&n-1と表せる。
■n & n-1 を繰り返して 0 になる直前が求める値となります。
n & n-1 が 0 にならないうちは n &= n-1; を繰り返せばよい
この0にならないうちは、とは今回の4のように0000になるまで繰り返すという意味でしょうか。
■while (n & n-1) n &= -1
while文はtrueのうちは繰り返す文なので、この文はn &= -1になるまで（n & n-1）を繰り返す、という意味になる。調べたところ、＆＝は代入演算子とわかりましたが、なぜn &= -1となるのでしょうか。上記では0になるまで、とあったのでそれを表しているのだと考えましたが合っていますでしょうか。
長くなってしまいましたが、ご助言いただければ幸いです。
よろしくお願いいたします。
0
"n 以下の最大の2のべき乗"
の部分を求める関数だけ。動作未検証。
C
1unsigned int f(unsigned int n) 2{ 3 return n <= 1 ? n : f(n >> 1) << 1; 4}
投稿2020/10/06 14:20
総合スコア4830
0
Quoraを参照して作ってみました。
#include <stdio.h> int BitScanReverse(unsigned word) { unsigned z; int n = 0; if (word == 0) return -1; if ((z = word & 0xffff0000) != 0) { n += 16; word = z; } if ((z = word & 0xff00ff00) != 0) { n += 8; word = z; } if ((z = word & 0xf0f0f0f0) != 0) { n += 4; word = z; } if ((z = word & 0xcccccccc) != 0) { n += 2; word = z; } return (word & 0xaaaaaaaa) ? n + 1 : n; } int main() { unsigned u = 0; scanf("%u", &u); int i = BitScanReverse(u); printf("%u\n", i < 0 ? 0u : (1u << i)); return 0; }
関数にしなくても
#include <stdio.h> int main() { unsigned u = 0, z; scanf("%u", &u); if ((z = u & 0xffff0000) != 0) u = z; if ((z = u & 0xff00ff00) != 0) u = z; if ((z = u & 0xf0f0f0f0) != 0) u = z; if ((z = u & 0xcccccccc) != 0) u = z; if ((z = u & 0xaaaaaaaa) != 0) u = z; printf("%u\n", u); return 0; }
でもよかった。
投稿2020/10/06 14:16
編集2020/10/06 14:50総合スコア478
0
この問題をどの関数を使って、解いたら良いか
main関数は必須として、数値を読み取るための関数(一つでやるならscanf()、いくつかの関数を組み合わせるならfgets()とstrtol()等)、と表示するための関数(printf()...それ以外は使ってもメリットないでしょう)だけで十分じゃないですか?
どうしても使いたければlog()を使ってもいいですけれど、この問題には大げさと思います。
ちなみに、そのタイトルそのまま「標準入力から非負整数値 n（ 0 ≦ n ＜ 2の31乗 ）を読み取り、n 以下の最大の2のべき乗を計算してその値を必要最小限の桁数で1行として標準出力に書き出すプログラム」でぐぐってみると、同様の問題が引っかかりますね。
投稿2020/10/06 13:28
編集2020/10/06 13:32
総合スコア7652
回答ありがとうございます。scanfを使って組むのを考えているのですが、それが一番シンプルにできそうですね。こちらも同じ問のようですね。答えが知りたいというよりはその構造が知りたかったのでこちらのご回答がとても有難いです。
修正前を見ていなかったのですが、誤りまで同じというのはなかなか興味深いですね。
競技プログラミングの類で、単純に問題をコピペすると累乗の記号が落ちる、とかいうことでしょうか。
0
（すみません問題を勘違いしていましたので最初の回答は削除しました。）
すでに色々な方から回答されているように色々な解法があると思いますが一例として参考までに動くコードを提示しておきます。
C
1#include <math.h> 2#include <stdio.h> 3 4int main() { 5 unsigned n, i = 0, ans = 0; 6 scanf("%d", &n); 7 if (n == 0) { 8 printf("0"); 9 } else { 10 while (ans * 2 <= n) { 11 ans = pow(2, i); 12 i++; 13 } 14 printf("%d\n", ans); 15 } 16}
入出力例（入力範囲最大値） 2147483647 1073741824 入出力例（サンプル） 128 128 入出力例（サンプル） 100 64 入出力例（サンプル） 2 2 入出力例（サンプル） 1 1 入出力例（入力範囲最小値） 0 0
投稿2020/10/06 13:22
編集2020/10/06 14:56
総合スコア303
回答ありがとうございます。unsignedをまだ学習しておらず、今後学習の中で出てきた際に参考させていただきます。ありがとうございました。
すみません。n以下の2のべき乗の最大値の部分を勘違いしていました。
0
上限が小さいので、2のべき乗の数を順番に計算していって、nを越えたらその1つ前という風に求めるのが簡単でしょう。
#追記
変な上限だと思ったら、0 ≦ n ＜ 231じゃなくて0 ≦ n ＜ 2の31乗ですか。
まあ、それでもたかだか32回ループなので、上記の方針で良いかと思います。
投稿2020/10/06 13:03
編集2020/10/06 13:34
総合スコア84645
ご回答ありがとうございます。はい、記載に誤りがありすみませんでした。nを超えるまで繰り返す方法で書いてみます。
intが4バイトだろうから、intの範囲で計算すると、上限に近い数に対しては「nを越えたらその1つ前」というのが出来ない（オーバーフローしてしまう）ので、long long int が8バイトならそれか double で計算してください。
あなたの回答
tips
プレビュー
