皆さんいろいろと知恵を絞って頂けたようで、ありがとうございます。
この問題は私がやや天狗になっていた頃採用担当の方に出題して
頂いた問題で、回答例を頂いたときの感動は今でも昨日の事の様に
思い出せる程です。
与えられた自然数(0を含む)が2のべき乗数か否か判定し
そのbooleanを返すインターフェイス isAPo2 を作成せよ
バイナリイメージで捉える
2のべき乗数は｢1, 2, 4, 8, 16, …｣という数ですが、これをメモリ上で
表現すると次のようになります。
10進数において10のべき乗数が｢1, 10, 100, 1000…｣と繰り上がって
いくのと同様、2進数のメモリ上で表現される2のべき乗数とはご覧の
ようにある桁のみが1、他が全て0となります。この特徴を念頭に額に
汗して書き出した私のコードは、次のようなものでした。
bool isAPo2( int n ) {
bool flag = false;
while( 0 < n ) {
if( n & 1 ) {
if( flag ) {
return false;
} else {
flag = true;
}
}
n >>= 1;
}
return flag;
}
値nが0以下のときループに入らずフラグの初期値falseを返します。
次にnが0より大の間、1の位を確認(行4)しながら右シフトをし続け、
1の回数が2回になればfalseを返し(行6)、最後まで抜ければtrue
がセット(行8)されたflagを返します(行13)。
同様の回答は、とっちゃんさんも示されています。場合によっては
ループ回数が少なくてすむ私のコードの方がすごいもんね＞＜ネ。
int isAPo2(int num)
{
int onBit;
onBit = 0;
while( num > 0 ){
if( num & 1 ){
onBit++;
}
num >>= 1;
}
return onBit == 1;
}
算数の問題として捉える
これと同じ発想で回答をしていただいたのが、Hirotowさんです。
public isAPo2(int num)
{
while(num > 2 && num % 2 == 0){
num /= 2;
}
return num == 2;
} 右シフトというのは、全てのビットを右に寄せる操作を指します。
桁を1つ下げることは2で割る(行4)ことと等しく、剰余が0(行3)と
いうことは1桁目のビットが0であることと等しくなります。ただし、
この判定方法だと1(=2^0)が除外されてしまうのが残念ですね。
マスクを動かす
ma2さんは原理は同じものの逆の発想で回答いただきました。
bool isAPo2(int num)
{
int mask = 1;
int cnt = 0;
for(int pos = 0;pos < (sizeof(int) * 8);pos++){
if( num & mask ){
cnt++;
}
mask <<= 1;
}
return (cnt == 1);
}
初期値1のマスクmaskを用意し、マッチングしながらマスクを
左シフト(行9)しています。これは｢1, 2, 4, 8…｣と2倍し続けて
いるということです。そして1の個数を数え(行7)、それが1個
であるか否かを返しています(行11)。これなら1もばっちり☆
出題者が提示された回答
ここまでは、言ってみれば王道。うんうん、そうだよねと頷く
もっともな回答です。答えあわせをするとき、パターンは色々
あれど原理は同じだろうと思っていると、次のような回答を
頂きました。
#define isAPo2( num ) ( num && !( num & num - 1 ) )
どうしてこれで題意が満たせるのか、お分かりでしょうか。
ぜひ考えてみてください。私は中々分かりませんでした。
よろしいでしょうか。それでは、解説に参りましょう。
1(2^0)の場合 !( 1 & 1 - 1 ) = true
4(2^2)の場合 !( 4 & 4 - 1 ) = true
20の場合 !( 20 & 20 - 1 ) = false
32(2^5)の場合 !( 32 & 32 - 1 ) = true
88の場合 !( 88 & 88 - 1 ) = false
こうして表にしてみると一目瞭然ですね。値から1を引き、さらに
その二つの論理積をとると、2のべき乗数なら0に、そうでないなら
0以外になります。従って、その否定が2のべき乗数か否かを指す
booleanなるのです。なお、0についてはnum &&ではじかれます。
与えられた自然数(0を含む)が2のべき乗数か否か判定し
そのbooleanを返すインターフェイス isAPo2 を作成せよ
この回答を理解したときの感動は、今でも思考の原動力となって
います。
と、いうわけで。
boolean isAPowerOf2( int num ) {
if (num <= 0) { return false; }
return !( num & (num-1) );
} 全くそのままの回答をされたれいさんに惜しみない拍手をー。
くるかな、くるかなとは思っていましたが、本当にくるとはー。
わんくまは怖いところです。
力尽きてしまったので一行返信なのです
黒龍さん：解説エントリーはまだですかー＞＜。
Ognacさん：解説エントリーはまだですかー2＞＜。
凪瀬さん：む、むむ？よく考えれば分かる…かも？
2リットルさん：コ、コンパイルできません＞＜。
も～ひと手間頂きたかったかもしれません。
dolanさん：くっ、黒龍さんのと同じく、どうしてこれでうまく
いくのか分からない。えーとC教本は…。
みきぬさん：今やっと理解しました。基数2指定で文字列変換し、
正規表現でマッチングですか。重そうだけどありだと思いますｗ。
Piz&Yuminaさん：なんとなくやりたいことは想像がつくのだけれど、
構文がよく分からなくて解読がー。基数2で文字列変換したデータを
ソースに…えーとえーと、あー＞＜。
επιστημηさん：そーきたかー＞＜ぱぱっとすーぎー。