用乘法代替右移
Replace right shift by multiplication
我知道可以用左移来实现乘以2的幂(x << 4 = x * 16)。
此外，将右移替换为二的幂 (x >> 5 = x / 32) 是微不足道的。
我想知道是否可以用乘法代替右移？
在一般情况下似乎不可能，但我的问题仅限于模 2^32 和 2^64 算术（无符号 32 位和 64 位值）。此外，如果我们可以添加其他廉价指令（如 + 和 - 除了 * 来模拟正确的位移位，也许可以做到这一点？
我假设异国情调的架构，其中右移比其他算术（类似于除法）更昂贵。
uint64_t foo(uint64_t x) {
return x >> 3; // how to avoid using right shift here?
}
有一个类似的问题，询问如何用右移替换两个无符号数的乘法。基本上，它在内部使用循环。然而，也许如果第二个数字是一个常数，这个循环可以避免（或者至少展开到一个更短的片段）？
"" 又名 high-mul、hmul、mulh 等，可用于模拟具有常量计数的右移。通常这不是一笔好交易。它也与 C++ 几乎没有关系。
普通乘法（撇开浮点数）不能用于实现右移。
my question is limited to modulo 2^32 and 2^64 arithmetic
没用。您可以使用 属性 来“反相乘”（有点像除法，除了不是真的）奇数，例如如果 b = 5 * a 那么 a = b * 0xCCCCCCCD，使用模乘逆。被反转的数字必须相对于模数是互质的。由于模数是2的幂，所以这里的“除数”不能是2的幂（1除外，但它什么都不做），所以不能这样右移。
另一种看待它的方式（可能更简单）是，乘法的作用是有条件地将一堆左移版本的被乘数加在一起。只有左移版本，没有右移版本。这些移位版本中的哪些被乘数 select 并不重要，没有右移版本到 select.
我知道可以用左移来实现乘以2的幂(x << 4 = x * 16)。
此外，将右移替换为二的幂 (x >> 5 = x / 32) 是微不足道的。
我想知道是否可以用乘法代替右移？
在一般情况下似乎不可能，但我的问题仅限于模 2^32 和 2^64 算术（无符号 32 位和 64 位值）。此外，如果我们可以添加其他廉价指令（如 + 和 - 除了 * 来模拟正确的位移位，也许可以做到这一点？
我假设异国情调的架构，其中右移比其他算术（类似于除法）更昂贵。
uint64_t foo(uint64_t x) {
return x >> 3; // how to avoid using right shift here?
}
有一个类似的问题
"
普通乘法（撇开浮点数）不能用于实现右移。
my question is limited to modulo 2^32 and 2^64 arithmetic
没用。您可以使用 属性 来“反相乘”（有点像除法，除了不是真的）奇数，例如如果 b = 5 * a 那么 a = b * 0xCCCCCCCD，使用模乘逆。被反转的数字必须相对于模数是互质的。由于模数是2的幂，所以这里的“除数”不能是2的幂（1除外，但它什么都不做），所以不能这样右移。
另一种看待它的方式（可能更简单）是，乘法的作用是有条件地将一堆左移版本的被乘数加在一起。只有左移版本，没有右移版本。这些移位版本中的哪些被乘数 select 并不重要，没有右移版本到 select.