3师没有分工

Question

我在一次采访中得到了这个问题来描述评论中的输出.

unsigned int d2(unsigned int a)
{
__int64 q = (__int64)a * 0x0AAAAAAAB;  // (2^33+1) / 3
return (unsigned int)(q >> 33);
}

我已经在Stackoverflow中检查了与除以3相关的其他问题,但没有一个看起来如此快速和小.任何人都可以帮我解释函数如何给出评论中写的输出？

Answer 1

该函数将32位无符号数除以3.

如果乘以2 ^ 33然后除以2 ^ 33(通过右移),则得到原始数字.但是如果你乘以(2 ^ 33)/ 3然后除以2 ^ 33,你实际上除以3.

最后一位数B而不是A导致结果向上舍入.

没有必要在代码中实际写入它,因为编译器通常会为您执行此操作.试试看吧.(此外,对于带符号的输入,编译器可以安全地生成带符号的右移,但C语言不会定义这样的操作.)