2のべき乗か否か

ある整数が、2のべき乗か否かを判別する、簡単で、なるべく高速なアルゴリズムは
無いでしょうか？

if (n == 0)
return false;
else
return ((n - 1) & N) == 0);

ビットパターンで、
・最上位ビットが1
・それ以外が0
なら2のべき乗。

32ビットまでだったら、単純に32回比較してやるのが案外一番はやいかもね

//2のべき乗であれば0を返す。
Uint32 Is2N(Uint32 bits)
{
bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
bits = (((bits >> 4) + bits) & 0x0f0f0f0f;
bits += bits >> 8;
bits + (bits >> 16)) & 0xff;

return (bits-1);
}

分岐一切なしだ、どうだ？

>>2
よく見直したら n が 0 でも使えるじゃないか。

>>5
分岐一切なしだ、どうだ？

return ((n - 1) & n) == 0);

>>6
まいりました。m(_ _)m

数学的センスってこういうところで出るのね

つーか２のべき乗を判定して何するんだ。

>6
n=0のときは使えないよ。
trueになる。

//2の何乗か数える
Uint32 Get2N(Uint32 n)
{
n--;
n = (n & 0x55555555) + (n >> 1 & 0x55555555);
n = (n & 0x33333333) + (n >> 2 & 0x33333333);
n = (((n >> 4) + n) & 0x0f0f0f0f;
n += n >> 8;
n + (n >> 16)) & 0xff;

return (n&31);
}

ノンブランチアルゴリズム、これならどうだ？

>>9

私もしりたい。なにに使うんだろう。高速化
しなければいけないんだから、余程何度も
実行される部分なんだろうな。

ま、頭の体操としても面白いが。

shiftで済ませられるときはそーしたいとか鴨

テクスチャの有効無効、シフトビット数の判定に使います。

#include <stdio.h>

int main()
{
double x,i=1;
printf("Input x > ");
scanf("%lf",&x);

while((i *= 2) < x);
if(x == i)
printf("true \n");
else
printf("false \n");

return 0;
}

訂正
double -> int
%lf -> %d
double じゃなくても良いですな。

#include <stdio.h>

int main()
{
int x;
printf("Input x > ");
scanf("%lf",&x);

while((x /= 2) > 2);
if(x == 2)
printf("true \n");
else
printf("false \n");

return 0;
}

あっ、2^0 = 1 に対応してへん・・・鬱だ詩嚢。

x = 0と2^0=1を勘違いしていた、鬱だ詩嚢。

リアル厨房の頃から思ってたんだけど・・・・・2^0が何で1になるの？
数学教師は大学生になれば解るって逝ってたけど、俺もう２５だよ(;´Д`)

＞リアル厨房の頃から思ってたんだけど・・・・・2^0が何で1になるの？
別にこれといって法則があるわけじゃないんです。
ただ、０乗を１として扱うことにより、都合が良いからです。
私はそう聞きました。
０乗を下手な数値として扱ったり、０として扱うと
都合が悪いそうです。

iValue % 2

>>17
これは無視しておいてね。

#include <stdio.h>

int main()
{
int x,i=1;
printf("Input x > ");
scanf("%d",&x);

while((i *= 2) < x);
if(x == i || x == 1)
printf("true \n");
else
printf("false \n");

return 0;
}

ミスばっかで後味悪いんで、とりあえず 2^0 = 1 にも対応版。
今日は調子が悪い。鬱だ、詩嚢。

＞２１
ありがと！でも何か理不尽だ(;´Д`)

n^0 = 1
の話が数学板にあったような気がするよ。

宿題スレにしてはもりあがったな。

なぜ ゼロ乗がゼロかって

１）級数展開してゼロを代入したら１だったから？

２） a/a=a^1*a^(-1)=a^(1-1)=a^0

>>27
うん、確かそんな感じの話しだった気がする（＾＾；

＞２７
オー！確かに２）を計算すると１になる。
スゲー！スゲーよ兄貴！１０年来の謎が解けたYo-
何か数学って楽しいかも？とか思った２５の春・・・鬱だ氏のう(;´Д`)

#include <stdio.h>

int main()
{
int x;
printf("Input x > ");
scanf("%d",&x);
if( !(x & (x-1)) && x )
printf("true \n");
else
printf("false \n");

return 0;
}
人のフンドシで相撲を取ってみたり〜♪

>>30
おっ、良い感じ。

ビット演算か・・・やるな
俺なら十日掛かるね

複雑なことを簡潔した形で表記した場合、
見た目はシンプルで良いんだが
理解するのに苦労するかもなぁ・・・。

^はxorじゃないのか…

>>30　でも、xを int にした為にバグを混入させちゃったね

>>35
どういうバグ？

そして0の0乗は未定義なんだな。

>>36
MSBだけが１の時は負数を表現してる事になる
たとえば１６ビットなら -0x8000　これは負数だから２の整数べき乗ではありえない

う〜〜ん・・・
>>30　のやつで、x = 1 、つまり x = 2^0 が true と
判別されるんだが・・・。一応使える。

Q) 2を底にした対数を固定小数点で求める
とかどうだ。

Assemberのマクロで昔書いた物だ...

２次方程式スレの１だけど
http://piza.2ch.net/test/read.cgi?bbs=tech&key=984447845
の　35　は log(n)に比例する時間で処理は出来るけど
それより早い方法があるのかな？

＞人のフンドシで相撲を取ってみたり〜♪
オラ、フンドシなんて身につけないんだけど、
パンツなら身に着けるぞ。
ところで、オラのパンツさ履いてどうだったべか？
履き心地はどうだべか？

int unko(int a)
int i;
int y;
for(i=1;i<1000000000;i++){
y=2;
y=y^i;
if(a==i){
return TRUE;
}
return FALSE;
}
どこまでも測定可能。

てゆーか、べき乗ってなんだっけ？

>>43　 ネタなんだよね？　でも突っ込みどう入れたらいいんだ？

>>44
検索エンジンで探せばすぐ見つかると思うんだが・・・。
辞書とかも使ってみては？

検索してきた。
なーんだそういうことか。じゃあ４３のでいいな。まさか１億もべき乗するやつなんていないだろう。
あっ、
if(a==0)
return FALSE;
を上のほうに入れてね！

あっまちがえた。
if(a==y){
return TRUE;
}
だった。

とりあえず47には
「1つの変数に1億ビット＝12.5メガバイト使う計算がどこにある！」
と突っ込んでおこう。

>>43-44 >>4-48
ね、ネタなんだよねぇ…？

>>50
世の中、君が思っているほどまともじゃない

俺の突っ込みも変だ。
まあ、金曜の夜で頭の中がテンパってるからなあ。
とりあえず、逝ってくるよ。

上ので何か問題が？

あ、unkoのうしろに｛つけてなかったからか・・・

>>53
int 型の数値の表現範囲を考えてみようや。

＞５５
ＶＣ＋＋６ではとおったんですが

>>51
ふむ。つーか俺も4-48って何やってるんだ…。

>>55
まぢれす。

・ ^ は累乗じゃねぇ。
・int y に 2 の 100乗だの1000乗だのなんざ入らん。
・return FALSE; の前で for の } を閉じろ。
・a==1 の時もTRUEになるようにしてやってくれ。
・aが２のべき乗じゃなかったら10億回ループしないとFALSEが帰ってこないのは嫌だぞ。

など。

またしくじった。
>>55 じゃなくて >>56 だ。逝ってくる。

なんと！^じゃなかったとは・・・
やばかった・・・
スマソです＞ＡＬＬ

>>59
榕ﾀ

つーか、コンパイラとおっただけで完成なんていってるからバグが
なくならんのよ。仕様ですか？

>>41 log(n)の nがなんだかわからんけど、
n桁の精度で求めるには log(n) でできたぞゴルァ。

#define FP_SHIFT 15 /* assert(FP_SHIFT * 2 + 2 < bit of int) */
#define FP(n) ((n) << FP_SHIFT)

int
log2(unsigned int n)
{
int v = 0;
int i, step;

if (n <= 0) return -1;

/* find most siginicant set bit: log(N) */
i = 16;
step = 8;
while ((n >> i) != 1) {
assert(step != 0);
if (n >> i) {
i += step;
} else {
i -= step;
}
step /= 2;
}

/* fix the interger part */
v = i - FP_SHIFT;
if (v < 0) {
n <<= (-v);
} else {
n >>= v;
}
v <<= FP_SHIFT;

/* calculate more precisely... */
for (i = FP(1) / 2; i; i >>= 1) {
assert(n >= FP(1) && n < FP(2));
n = (n * n) >> FP_SHIFT;
if (n >= FP(2)) {
v += i; n /= 2;
}
}
return v;
}

せっかくテストルーチン削ったのに省略されてるじゃねえか。
ffs(3) 相当のことを O(log(n)) でやってるけど、
BSDの ffsの実装見てみたら O(n) だったぞ。n= bit数だけど。

全然関係ないけど、CORDICってもー流行らないのかなあ

http://www.ascii.co.jp/ghelp/66/006654.html
↑より参照

コンピュータで扱う最小の情報単位であるビット（2進数の1桁ずつ）に対する演算。
基本的な演算命令として「and」「or」「not」などがある。
データ読み書きでは、ビットを8桁分並べたバイトという単位が最小の単位になる。

ってことは、２のべき乗（０乗は除く）にのみビット演算が有効ってわけ？

>>65
　たとえばmod演算とかも２のべき乗には１命令で出来ます。
n mod 8 = n and 7

　が、2のベキ乗でない mod 演算も、これを利用して実現する事が可能です

typedef int INTTYPE;

BOOL Hikaku(INTTYPE i)

INTTYPE j = 1;
do {
if ( i == j ) return TRUE;
if ( i < j ) return FALSE;

j <<= 1;
} while ( j != 1 )

return FALSE;
}

じゃだめかな？

しまった

INTTYPE は unsigned 限定だ(^^;

>>62
　2分検索でMSBの位置を見つけるアイデアって事なんだね

最下位の setされた bitだけを立てる:
#define LSSB(n) ((n) & ~(n-1))

>>62

個の場合数えるべき演算数は総シフトビット数(vビットのシフトの
コストは v) だから、これ log n じゃないと思われ。

というか、桁数が大きくなったときのことを考えれば、 > 演算も
O(n) だからそもそも使えない。ビット数は高々定数値 (32とか)
というなら、bsd のやり方でも constant order で優劣は無い。

ごめん。ビットシフトはインデックスの演算で処理できるから、
62 のコストは比較演算子の n で、log n 回だけ回るのでこの
アルゴリズムは order n log n 、となる、のか。

>>2 >>6 で答え出てるじゃん

70だけど ((n) & -(n)) で良かったのか。鬱。

>>74
70だと負数が 1 の補数でも使えるから汎用性が高いよ。
（まったく無意味なコメントでごめんね）

>>71 多倍長のことは考えてないっす。
shiftと比較が O(1)でできるって前提で。
まあ、constant orderなのはたしかだけど、
高々 5回の比較でできるってことで。

ROL(unsigned &dt, int n) がスマートに書けない。

ループになら書けるんだけどなあ
int i;
for(i=0;i<n;i++){
r<<=1;
if((dt) & 0x80000000){dt=(dt<<1)|1}; else (dｔ)<<=1;
}

>>77
return (dt<<n) | (dt>>(sizeof(int)-n));

間違い
return (dt<<n) | (dt>>(sizeof(int)*8-n));

しかし，のぐーさんってこんなとこにも顔出しているんだ。>> 1

>>78
　おお！　感激です
　こんなことがしたかったんで、
bitGet(unsigned &dt, int n)
{ unsigned r = dt & ( ( 1u<<n ) -1 );
　ROL(dt,n);
　return r;
}
bcc32だとROLでループ使ってるとinline展開されなかったんですよ

話をさかのぼって申し訳ないが，0乗について高校の教科書では >>27 2) の形
で説明をしているものが多いです。私自身は「a^n は 1 に a を n 回かけた
もの」と教えているので 0 乗を特別扱いしません。

>>82
その考え、おかしいし通用しないよ。

>>83
>>82は小学校の教師でしょ。
小学生にはわかり易い説明だと思うよ。
中高生には通用しないけど。

>>84
けどさぁ、最初から１があるのはおかしい。
確かにどの数字にも、その数字自体に１を掛けたものと
考えてもつじつまはあるけど、最初から１にとある
数値を掛けるってのはやっぱり変。
とある数値に１を掛けても、結果は変わらないというのなら
話しはわかる。
よって、上にあげられた説明はおかしい。

もっと突っ込むと、
＞a^n は 1 に a を n 回かけた
この a を n 回掛けた数値自体が何なわけ？
つまりこれが１だといっているようなもん。
だったら最初の１は要らねーだろ。

＞a を n 回かけた
さらに、a を n 回というのにおいて、
n が ０だった場合、つまり０乗だった場合、
a が何であろうと、具体的な数値は出てきません。
０乗が１だという定義がなければ、８２の結論は
出てこないはず。

x=a*b^c として、
c=0のときx=aじゃないの？
と言うわけで、b^0=1だと思うけど。

掛け算・割り算のデフォルト値は1、足し算・引き算のデフォルト値は0でしょう。

>>88
どうして？

a * b は、a を b 回加算したもの、
a ^ b は、a を b 回掛け合わせたもの、

それぞれ b が 0 の時は単位元の 0 と 1 になる、
これが基本。ついでにいえば and の単位元は 1、
or の単位元は 0。

89 の「どうして」は、大きな「どうして」なんで、
僕には答えられない。数論を一から再記述するのは
とても大変だし、ほかの「どうして」が山ほどでて
くるだけだから。

>>90
a^n がどうのこうの言う前に、
>>82
＞a^n は 1 に a を n 回かけた
についておかしいといっているのだ。
なぜ最初に１に何かを掛けるのか？
別に間違いじゃないが、a^0 = 1 じゃなきゃ
これは成り立たない。
それに a を 0 回掛けた値が最初から１だと
言っているわけであり、どこからか
a^0 = 1 が出てしまっているのに、
なぜかわざわざワケの分からない考え方をしているか。
a^0 = 1 を説明するには不十分だ。

aの1乗はaである。という仮定から出発して、aをさらにかける（2乗になる）場合には、答えはa*aになる。べき乗の数が増えればかけざんの数が増える。逆にべき乗の数が減ることは掛け算の数が減る…という一面的な見方だけでなく、aで割るという見方もできる。これは全く意味的に一緒。だから、aの1乗がaであれば、aの0乗は、a/aで1ということで良いのではないですか？初心者ですけどでしゃばってみたんですが。

α^x:=α×α×... (x回繰り返し)

という定義からはα^0は出てこない

定義より

α^x×α^y=α^(x+y)

ここで負数の累乗を考える

α^x×α^-y=α^(x-y)

から

　 　 　 　 1
α^-y=−−−
　 　 　 α^y

で
　 　 　 　 　 　 　 　 　 　 　 α^x
α^x × α^-x = α^0 =−− = 1
　 　 　 　 　 　 　 　 　 　 　 α^x

となってキレイだからα^0=1と負数の累乗は導入された
つーか久しぶりに数I思い出したよ。

a^0 = 1 の証明について
おかしな説明をしているといってるのであり、
a^0 = 1 を証明しろと言っているわけではないのだが・・・。

>>94
a^0 = 1 の証明について
おかしな証明をしていたんだとしても
>>93 ので納得すればいいんじゃないの？

ていうかプログラマ―には理屈は不要。
あんた達は我々の出す仕様にのっとって
コードを吐きつづければいいのだよ。

>>95
あんた、>>82を見たか？
何偉そうに（プ

一見当り前なことを証明するには背理法。

♪ポケットの中にはビスケットが一つ、
　ｎ回叩けばビスケットは２のｎ乗

a^0 = 1は証明すべきものでなくて単なる定義です。
a^xのx→0の極限が１ってだけのもの。
だから１としといたほうがa^xがxの全域で連続になるから
そうしているだけです。

別に極限使わなくても良いような...
そもそも a = 0 のときは、極限は 1 じゃないし...

a^0≠1として系を組んでみればよろしい。
もしかしたら画期的な公理系が発見できるかもよ？
習ったコトが「正しい」とは思わないことだ。
単に現実的に「便利」だから、採用されているに過ぎないのだよ＜現在の公理系
マニュアル文化に育った馬鹿どもか？おまーら？

0 ^ n は n <= 0 の時定義されていないんじゃない？
a^0 ≠1 の例としては面白くないけど。

>>101
あんたが一番バカなお答えをしています。

なんで馬鹿が多いんだか
０乗の値は単なる定義なの！別に１００でも２００でもそう定義すれば
それでもＯＫなんだけどa^xのx=0での連続性を要求するとa^0を１と
定義したほうが都合がいいってだけの話。

>>104
そう、そういうこと。

ビスケットの話でいいと思うけど、連続性を要求云々はおかしい。
数学(解析学)だと一般の指数関数はeを底にする場合の拡張で、
よく知られているように
exp x = 1 + x/1! + x^2/2! + x^3/3! ... x^n/n! ...
です。これは、解析学では、指数関数を「展開した式」ではなく、
指数関数の「定義」です。
exp 0 は極限とは関係なく当然 1 です。

もうここまでくると哲学の域だな。

2 や 3　の定義を考えてみれば、 n^1 = 1 x n というのも別におかしくないような気がするが、ここまでくると単に混乱してるだけかもしれん。

てつがく 【哲学】

〔（ギリシヤ） philosophia は知恵への愛・希求の意。
西周（にしあまね）の訳語。賢哲の希求を表すために「希哲学」と訳したが、後「哲学」とした〕

（1）世界や人間についての知恵・原理を探究する学問。
もと臆見や迷妄を超えた真理認識の学問一般をさしたが、
次第に個別諸科学が独立し、通常これらと区別される。
存在論（形而上学）、認識論（論理学）、実践論（倫理学）、
感性論（美学）などの部門をもつ。

（2）自分自身の経験などから得られた基本的な考え。人生観。「社長の経営術には一つの―がある」

>>108
さすがに字引の解説は文句のつけようがないぐらい
妥当な説明だな。

いや，基礎論方面出身者としては気になる発言も多々あるのですが，
話をかき乱してしまって申し訳ないです。ただ，0乗が1であることを
前提にしているのではなく，乗法での単位元が1であることを前提に
しているだけだということは申し上げておきます。そもそもこの説明
だけで済ませることはありません。というかだいたいこのやり方は普
通の説明をしたあとで納得しない生徒を納得させる「手」の一つにす
ぎません。たとえば「aのn乗ってどういうこと？」と何人かに聞くと
「aをn回かけたもの」と答える者がいるので，「じゃぁ1乗は1回かけ
るんだよね。何にaを1回かけるんだろう」と聞くと1にかけたものであ
ると答えざるをえなくなります。もちろん言葉遊びではあるわけです
が，これで0乗を1とするのは妥当なものかもしれないという方向に生
徒の気持が動きかけたら，そこで元の普通の説明に戻ってたたみかけ
る，とかそんなことをするわけです。

そういう背景で使うやり方だということを説明せずに書いてしまった
ことで混乱を招いたことをお詫びします。

>>108
最後の「などの部門をもつ」というところが、何ともかわいいですね。

>>110
なるほど。まっ、完全に間違いってわけじゃないね。
う〜〜ん、難しい。

仕様です！

さすが高校教師 >> 110

>>104
何気に大嘘書いてるのがいるな。0^0=1だろ。

×>>104
○>>102

誤爆ｽﾏｿ

>>115 ネタですか? 0^0 は未定義

で，元ネタは某 Nifty の某掲示板なんですが...

えぴすてーめーとか，その他，かっこつけている連中がどうしようもない
コードをこねくり回している間に 2ch では正解（というかエレガントな解）
がでていたのだよ。狭い井戸で吼えてるカエルどもの程度が知れてたのしかったわい。

>>82あたりからの展開を見ると、この板は馬鹿が多そうだ。

そりゃぁ2ちゃんねると@niftyの会議室では反応速度が違うでしょう。

0^0 = 1 と一般に言われるなら、
やはり０乗は１だ！と定義しているようなもんですよね。
０自体何を掛けても０ですし・・・。

> 0^0 = 1 と一般に言われるなら

前提が既に偽。

0^-1 は・・・なんだ？

>>114 う，素性を知ってる人がいる(--;
>>123 0 を分母にもっていってはいかんでしょう。

いまプログラム書いていて、何気にこのルーチン使う機会があったので報告。
冪乗で増加する分布P(k)=k^{\gamma}を出力するときに

if(!(k&(k-1))&&k) fprintf(fp, "%d %f\n", k, P[k]);

で出力すると対数プロットをしたときにデータが等間隔になってハッピーです。

はう既出だった。さらば。