编译器将对
除以常数进行优化,转换为
乘以倒数或乘法逆元。例如,
x/12
将被优化为
bool h(uint16_t x)
{
return x % 12 == 1;
}
h(unsigned short):
movzx eax, di
imul eax, eax, 43691 ; = 0xFFFF*8/12 + 1
shr eax, 19
lea eax, [rax+rax*2]
sal eax, 2
sub edi, eax
cmp di, 1
sete al
ret
由于SSE/AVX中有乘法指令,因此可以轻松进行向量化。此外,x = (x % 12 == 1)?1:0;
可以简化为x =(x%12 == 1)
,然后转换为x =(x-1)%12 == 0
,从而避免从常量表加载值1进行比较。您可以使用向量扩展 ,让gcc自动生成代码。
typedef uint16_t ymm32x2 __attribute__((vector_size(32)));
ymm32x2 mod12(ymm32x2 x)
{
return !!((x - 1) % 12);
}
以下是gcc的mod12(unsigned short __vector(16)):
vpcmpeqd ymm3, ymm3, ymm3 ; ymm3 = -1
vpaddw ymm0, ymm0, ymm3
vpmulhuw ymm1, ymm0, YMMWORD PTR .LC0[rip] ; multiply with 43691
vpsrlw ymm2, ymm1, 3
vpsllw ymm1, ymm2, 1
vpaddw ymm1, ymm1, ymm2
vpsllw ymm1, ymm1, 2
vpcmpeqw ymm0, ymm0, ymm1
vpandn ymm0, ymm0, ymm3
ret
Clang和ICC不支持向量类型的!!
,因此您需要改为(x - 1) % 12 == 0
。不幸的是,编译器似乎不支持__attribute__((vector_size(8)))
来发出MMX指令。但现在您应该使用SSE或AVX。
如上面的Godbolt链接所示,x % 12 == 1
的输出更短,但您需要一个包含1s的表进行比较,这可能更好也可能不是。编译器无法完全优化手写代码,因此可以尝试使用内部函数将代码手动向量化。检查哪一个在您的情况下更快。
更好的方法是((x * 43691) & 0x7ffff) < 43691
,或者如nwellnhof的答案中所述,x * 357913942 < 357913942
,这也应该很容易向量化。
或者,对于像这样的小输入范围,可以使用查找表。基本版本需要一个65536元素的数组。
#define S1(x) ((x) + 0) % 12 == 1, ((x) + 1) % 12 == 1, ((x) + 2) % 12 == 1, ((x) + 3) % 12 == 1, \
((x) + 4) % 12 == 1, ((x) + 4) % 12 == 1, ((x) + 6) % 12 == 1, ((x) + 7) % 12 == 1
#define S2(x) S1((x + 0)*8), S1((x + 1)*8), S1((x + 2)*8), S1((x + 3)*8), \
S1((x + 4)*8), S1((x + 4)*8), S1((x + 6)*8), S1((x + 7)*8)
#define S3(x) S2((x + 0)*8), S2((x + 1)*8), S2((x + 2)*8), S2((x + 3)*8), \
S2((x + 4)*8), S2((x + 4)*8), S2((x + 6)*8), S2((x + 7)*8)
#define S4(x) S3((x + 0)*8), S3((x + 1)*8), S3((x + 2)*8), S3((x + 3)*8), \
S3((x + 4)*8), S3((x + 4)*8), S3((x + 6)*8), S3((x + 7)*8)
bool mod12e1[65536] = {
S4(0U), S4(8U), S4(16U), S4(24U), S4(32U), S4(40U), S4(48U), S4(56U)
}
只需将x % 12 == 1
替换为mod12e1[x]
即可使用。当然,这也可以进行矢量化处理。
但由于结果只有1或0,因此您还可以使用65536位数组将其大小减小到仅8KB。
您还可以通过4和3的整除性来检查12的整除性。显然,4的整除性是微不足道的。可以通过多种方式计算3的整除性:
一种方法是计算奇数位数字之和与偶数位数字之和的差值,例如גלעד ברקן的答案中所示,并检查它是否可被3整除。
或者,您可以检查在基于2的2k(如基于4、16、64...的基数)下的数字之和,以查看它是否可被3整除。
这种方法之所以有效,是因为在基数为b
时,要检查任何除数n是否能被b - 1
整除,只需检查数字之和是否能被n整除。以下是实现:
void modulo12equals1(uint16_t d[], uint32_t size) {
for (uint32_t i = 0; i < size; i++)
{
uint16_t x = d[i] - 1;
bool divisibleBy4 = x % 4 == 0;
x = (x >> 8) + (x & 0x00ff); // max 1FE
x = (x >> 4) + (x & 0x000f); // max 2D
bool divisibleBy3 = !!((01111111111111111111111ULL >> x) & 1);
d[i] = divisibleBy3 && divisibleBy4;
}
}
将3整除的功劳归功于Roland Illig
由于自动向量化的汇编输出过长,您可以在如何判断一个二进制数是否能被3整除?
确定一个二进制数是否能被3整除
位表示和3的整除性
构建可判断3的整除性的电路
检查一个数字是否能被3整除
检查一个数字是否能被3整除的逻辑?
==
操作符扩展到整数类型时,它已经返回1
表示真和0
表示假。 - Ben Voigtbool-expression ? 1 : 0
更易读,因为它不依赖于双关语(即比较运算符的结果实际上不是布尔值,而只是整数0或1)。在C++中,这是一种隐式类型转换。在其他语言中,您可能会得到类型不匹配的错误,甚至结果可能是-1
。 - Raymond Chen