斯坦福的bithacks代码非常不够优化。为了完整起见,这里是在所有平台和环境中最好的代码:
#include <stdint.h>
#if !defined(__wasm__) && defined(__cplusplus) && defined(__cpp_lib_bitops)
# include <bit>
# define paritytree_parity32(x) (std::popcount(x) & 1)
#elif !defined(__wasm__) && defined(__has_builtin)
# if __has_builtin(__builtin_parity)
# if INT_MAX >= INT32_MAX
# define paritytree_parity32(x) __builtin_parity(x)
# else
# define paritytree_parity32(x) __builtin_parityl(x)
# endif
# endif
#endif
#if !defined(__wasm__) && defined(_MSC_VER) && defined(_M_X64) && !defined(paritytree_parity32)
# include <intrin.h>
# define paritytree_parity32(x) __popcnt(x)
#elif !defined(paritytree_parity32)
static inline uint32_t paritytree_parity32(uint32_t v) {
v = (v ^ (v << 1)) & 0xAAAAAAAA;
return (v*5 & UINT32_C(0x88888888)) * UINT32_C(0x11111111) >> 31;
}
#endif
以下是用于显示汇编代码的测试C代码:
uint8_t fastParity(uint32_t x) {
return paritytree_parity32(x);
}
在x86_64架构上,Clang 17和GCC 13都能生成这个精彩的代码。请注意它如何利用x86的16位半寄存器来减少2条移动和移位指令。还请注意`setnp`,这是一个鲜为人知的x86宝石,它获取由xor操作影响的奇偶标志寄存器的值。没错!每个16位xor操作都会根据目标结果的奇偶性设置奇偶标志。请参阅
https://c9x.me/x86/html/file_module_x86_id_288.html。
fastParity:
mov eax, edi
shr eax, 16
xor eax, edi
xor al, ah
setnp al
ret
在x86_64上使用MSVC 2019编译,它会产生这个结果。请注意,popcnt至少需要2008年的英特尔Nehalem(第一代)处理器,而Windows 10至少需要2017年的英特尔Coffeelake(第八代)处理器,因此在不支持的硬件上运行不是一个问题。
; MSVC 2019 on x86_64
fastParity PROC
popcnt eax, ecx
ret 0
fastParity ENDP
GCC在arm64上生成了这个:
; gcc 13 on arm64
fastParity:
fmov s0, w0
cnt v0.8b, v0.8b
addv b0, v0.8b
fmov w0, s0
and w0, w0, 1
ret
在arm64上,Clang生成了以下内容:
; clang 17 on arm64
fastParity: // @fastParity
eor w8, w0, w0, lsr #16
eor w8, w8, w8, lsr #8
eor w8, w8, w8, lsr #4
eor w8, w8, w8, lsr #2
eor w8, w8, w8, lsr #1
and w0, w8, #0x1
ret
MSVC在arm64上生成了以下内容:
|fastParity| PROC
eor w8,w0,w0,lsl #1
and w8,w8,#0xAAAAAAAA
add w8,w8,w8,lsl #2
and w9,w8,#0x88888888
mov w8,#0x11111111
mul w8,w9,w8
lsr w0,w8,#0x1F
ret
ENDP
生成的WebAssembly是:
(func $fastParity (
(i32.shr_u
(i32.mul
(i32.and
(i32.mul
(i32.and
(i32.xor
(i32.shl
(get_local $0)
(i32.const 1)
)
(get_local $0)
)
(i32.const -1431655766)
)
(i32.const 5)
)
(i32.const -2004318072)
)
(i32.const 286331153)
)
(i32.const 31)
)
)
这个WebAssembly没有内存或浮点数访问,不需要额外的检查器代码,所以它应该编译成这个漂亮小巧的x86_64。
fastParity:
lea eax, [rdi+rdi]
xor eax, edi
and eax, -1431655766
lea eax, [rax+rax*4]
and eax, -2004318072
imul eax, eax, 286331153
shr eax, 31
ret
而且这是在arm64上的情况:
fastParity:
eor w9, w0, w0, lsl #1
mov w8, #286331153
and w9, w9, #0xaaaaaaaa
add w9, w9, w9, lsl #2
and w9, w9, #0x88888888
mul w8, w9, w8
lsr w0, w8, #31
ret
为了比较,这里是Stanford bithacks页面上非常次优的C代码和生成的汇编代码。有3条额外的汇编指令,并且没有测试更快的硬件特定奇偶指令。
uint32_t stanfordParityDoNotUse(uint32_t v) {
v ^= v >> 1
v ^= v >> 2
v = (v & 0x11111111U) * 0x11111111U
return (v >> 28) & 1
}
stanfordParityDoNotUse:
mov edx, edi
shr edx
xor edx, edi
mov eax, edx
shr eax, 2
xor eax, edx
and eax, 286331153
imul eax, eax, 286331153
shr eax, 28
and eax, 1
ret