テーブルが間違ってたバグを修正しました(汗) 感謝>ingktさん
3の倍数を除算を使わずに判定したいという話を聞いたので、ちょっと考えてみました。
2進数表示を考えて2桁ごとに区切ります。それぞれ0~3までの数字と捉えて、足し算します。足し算の結果が3で割り切れれば3の倍数です。
372 → 101110100b
→ 1b + 01b + 11b + 01b + 00b
= 1 + 1 + 3 + 1 = 6
(参考にしたサイト) No.055 「111」は「3」の倍数(原理は一緒)
intが32bitの場合(0-0xfffffffeまでテスト済)。
#define MUL3TABLE 0x49249248 // bit31 to 0
int mul3test(unsigned int x) {
int i;
int c=0;
for(i=0; i<16; i++,x>>=2) {
c += (x & 3);
}
if (c>30) c-=27;
return (MUL3TABLE >> c) & 1; // if multiple 3 return 1
}
16bitの場合。
#define MUL3TABLE 0x9248; // bit15 to 0
int mul3test(unsigned int x) {
int i;
int c=0;
for(i=0; i<16; i++,x>>=2) {
c += (x & 3);
}
if (c>15) c-=12;
return (MUL3TABLE >> c) & 1; // if multiple 3 return 1
}
}
「3の倍数」ではなくて3で割り切れるかどうかを判定する場合は、
#define MUL3TABLE 0x49249248 // bit31 to 0
#define MUL3TABLE 0x9248; // bit15 to 0
をそれぞれ、
#define MUL3TABLE 0x49249249 // bit31 to 0
#define MUL3TABLE 0x9249; // bit15 to 0
と修正してください。
改良 2010/05/14
ts1さんのコメント通り改良したもの。
int mul3test2(unsigned int x) {
x = ((x >> 2) & 0x33333333) + (x & 0x33333333); // 0 to 6
x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f); // 0 to 12
x = ((x >> 8) & 0x00ff00ff) + (x & 0x00ff00ff); // 0 to 24
x = ((x >> 16) + x) & 0x0000003f;
if (x>30) x-=27;
return (MUL3TABLE >> x) & 1; // if multiple 3 return 1
}
ingktさんの改良案。2bitずつ加算しなくてもいいのは気付かなかった(汗)
int mul3test3(unsigned int x) {
x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
x = (x >> 8) + x;
x = (x >> 16) + x;
x = ((x >> 4) & 7) + (x & 0xf);
return (MUL3TABLE >> x) & 1;
}
実行速度0~0xfffffffeまで。gcc -O3でコンパイル。
real 2m10.451s
user 2m10.400s
real 1m28.912s
user 1m28.900s
real 15.719s
user 15.700s
非力なマイコンだとしても、ingktさんの実装が一番スマートですね。