入力されたｎ以下で最大の2のべき乗

Question

###やりたい事
0以上で2147483648未満のｎを読み取った後に、n 以下の最大の2のべき乗を計算して出力する。
###注意
読み取ったｎが0 の時は0を出力。

#include<stdio.h>
int main(void){


long int n;
long int b;

scanf("%ld", &n);
//計算はfor文？
for(nが2の31乗以下を確認？)
//どうやってｎ以下の最大の2のべき乗を毎回確認するのか．．．？
．．．

if(n==0){
   k=n;
    }

printf("%ld\n", b);

return 0;
}

Answer 1

#include<stdio.h>
int main(void) {

    long int n;
    long int b;
    int t;

    scanf("%ld", &n);

    t = 0;
    for ( b = 1L; b*2L <= n; b *= 2L ) {
      ++t;
    }
    printf("2^%d = %ld (< %ld)\n", t, b, n);

    return 0;
}

Comments

[ta-9]

ご回答有難うございます。
シンプルでとても分かりやすかったのでベストアンサーにさせて頂きます。

[raccy]

ベストアンサーを決めるのはいいですが、32bit環境またはWindowsの64bit環境で2147483647を入力したときにどのようになるかぐらいは確認してから提出した方がいいですよ。

[kazuma-s]

n が 1073741824～2147483647 のとき正しく動かないコードがなぜベストアンサーなんだろう。long が 64ビットの環境でしか確かめていないのだろう。

[katoy]

> ... 正しく動かないコードがなぜベストアンサーなんだろう ....
ベストアンサーを決めるのは 質問者です。
問題解決ができなかった人は、その問題の細かな点 / 微妙な点を理解できていないわけです。

お宝鑑定で、持ち主と専門家での評価が大きく異るのことが多いのと似たような状況なのだと思います。

Answer 2

long int で扱う, unsigned long int で扱う、
上位側から 1 が立っている最初のビットを探す、下位がわから 1 が立っている最後のビットを探す
の方法の組み合わせの 4つのメソッドを書いてみました。
x.c

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

long int get_largest_2pow_0(long int n) {
    if (n == 0) {
    return 0;
  }
  long int ans = 1;
  while (ans > 0 && ans <= n) {
    ans = ans << 1;
  }
  return labs(ans / 2);
}


long int get_largest_2pow_1(long int n) {
  if (n == 0) {
    return 0;
  }
  long int ans = -1;
  while (ans & n) {
    ans = ans << 1;
  }
  return -(ans >> 1);
}

long int get_largest_2pow_u0(unsigned long int n) {
  unsigned long int ans = 1L;
  while (ans <= n) {
    ans = ans << 1;
  }
  return ans >> 1;
}

long int get_largest_2pow_u1(unsigned long int n) {
  if (n == 0) {
    return 0;
  }
  unsigned long int ans = ~0;
  while (ans & n) {
    ans = ans << 1;
  }
  return (~ans >> 1) + 1;
}

int main(void) {
  long int data[] = {
    // -1, 
    0,
    1, 2, 3, 4, 5, 7, 8, 9,
    (1 << 7) - 1, 1 << 7 , (1 << 7) + 1,
    (1 << 15) - 1, 1 << 15, (1 << 15) + 1,
    2147483646, 2147483647,
    LONG_MAX - 1, LONG_MAX
  };

  for(int i = 0; i < sizeof(data) / sizeof(long int); i++) {
    long int num = data[i];
    printf("%ld -> %ld, %ld, %ld, %ld\n", 
      num,
      get_largest_2pow_0(num), get_largest_2pow_1(num), 
      get_largest_2pow_u0(num), get_largest_2pow_u1(num));
  }
  return 0;
}

実行例：

このコードでは いずれも 順番にビットをしらべています。
(0x1, 0x10, ... 0x10000000) のテーブルを用意して、2分法で 最上位のビット１を探すという方法もありかもしれません。(数をあてるHight & low ゲームみたいに)

でも ビット演算にはとんでもないテクニックがいろいろあります。
質問文の問題は 左からビットみていったとき 最初に 1 が現れる位置をもとめることと同じです。
興味があれば、こういった方法も研究してみるとう良いです。下の参考情報ページなどを読んでみてください。

参考情報

• データ型の最大値と最小値の一覧【32/64bit環境 limits.h/stdint.h】

https://marycore.jp/prog/c-lang/data-type-min-max-values/

• ビット演算あれこれ

http://marupeke296.com/TIPS_No17_Bit.html

• de Bruijn sequenceを用いたLSB/MSB位置検出テクニック

https://onihusube.hatenablog.com/entry/2019/09/20/230416

• ++11で実装するNTZとNLZ

https://qiita.com/kazatsuyu/items/38203287c19890a2b7c6

Answer 3

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

int main(void)
{
	uint_fast32_t n;
	if (scanf("%" SCNuFAST32, &n) != 1 || n >= (1ul<<31)) return 1;
	uint_fast32_t x = 1;
	while (x <= n) x *= 2;
	printf("%" PRIuFAST32 "\n", x / 2);
	return 0;
}

Answer 4

プログラミング以前の問題です。

どうやったら解けるか、もちろんコンピュータに解かせるのに適した解法というのもありはしますが、まずは「数学」(あるいは算数)の問題として日本語と数式で解き方を考えてからそれをプログラムに落とし込みましょう。

(「プログラミング言語で考える」なんてのは相当に非人間的作業です。出来なくて当然。)

2を底とする対数の整数部を求める、なんていう手法もありかなぁ...今回は前の質問より桁数が少ないから、コンピュータでの実現にも気を使わない。

ところで、nは整数、とか勝手に決めちゃっていいんでしょうか?

Comments

[coco_bauer]

2を底とする対数の整数部を求める、というのが素直な解法のように思います。
”2を底とする対数を求める”、"その整数部を求める"はプログラム言語で記述すれば良いので。

「nは整数、とか勝手に決めちゃっていいんでしょうか」　＜－　nは、”scanf("%ld", &n);”で値が入れられているので、整数でしょう。
　nが0以下の整数の場合は”解無し”になってしまうので、チェックは必要ですが。

[thkana]

> nは、”scanf("%ld", &n);”で値が入れられているので、整数でしょう。
そのコードがどういうものか、なんの説明もないんですよね。出題者が提示したものか、それとも先輩から引き継いだ「遺産」なのか。まえの平方根の問題では、なぜかいくつかの質問が、何年かに渡って(int)sqrt(x);ってなコードを書いていたりしたし。ということで、書いてあるコードは「不明」なので無視しています。

> nが0以下の整数の場合は”解無し”になってしまう
そちらは、nは0以上、とnが0のときは0を返すとの説明があるので。

Answer 5

解決済みですが、再帰関数で書いてみました。動作未確認。

unsigned int largetstPowerOf2(unsigned int n)
{
  //nがゼロの場合は答えが存在しないので、nは1以上とします。
  return (1 == n) ? 1 : largestPowerOf2(n >> 1) << 1;
}

Answer 6

#include <stdio.h>

int main(void)
{
    int n;
    scanf("%d", &n);
    n |= (n >> 1);
    n |= (n >> 2);
    n |= (n >> 4);
    n |= (n >> 8);
    n |= (n >>16);
    n -= (n >> 1);
    printf("%d\n", n);
}

別解

#include <stdio.h>

int main(void)
{
	int n;
	scanf("%d", &n);
	while (n & n-1) n &= n-1;
	printf("%d\n", n);
}

Answer 7

#include <stdio.h>
#include <inttypes.h>
int main(void){


    uint32_t n;
    uint32_t b;
    
    scanf("%"PRId32, &n);
    b=n;
    b = (b & 0xFFFF0000) ? (b & 0xFFFF0000) : b;
    b = (b & 0xFF00FF00) ? (b & 0xFF00FF00) : b;
    b = (b & 0xF0F0F0F0) ? (b & 0xF0F0F0F0) : b;
    b = (b & 0xCCCCCCCC) ? (b & 0xCCCCCCCC) : b;
    b = (b & 0xAAAAAAAA) ? (b & 0xAAAAAAAA) : b;
    
    
    printf("%"PRId32"\n", b);
    
    return 0;
}

Answer 8

2のべき乗を算出し、nと比較すればいいんでは