nabeの雑記帳

テーブルが間違ってたバグを修正しました（汗）　感謝＞ingktさん

３の倍数を除算を使わずに判定したいという話を聞いたので、ちょっと考えてみました。

方法

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
}
}

判定に０を含める場合

「３の倍数」ではなくて３で割り切れるかどうかを判定する場合は、

#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でコンパイル。

mu3test()
real    2m10.451s
user    2m10.400s
mu3test2()
real    1m28.912s
user    1m28.900s
mu3test3()
real    15.719s
user    15.700s

非力なマイコンだとしても、ingktさんの実装が一番スマートですね。