CODEWITHSUNDEEP
c++bit-manipulation
Curious
Curious

Reputation: 557

Replace right shift by multiplication

I know that it is possible to use the left shift to implement multiplication by the power of two (x << 4 = x * 16). Also, it is trivial to replace the right shift by division by a power of two (x >> 5 = x / 32).

I am wondering is it possible to replace the right shift with multiplication? It seems to be not possible in the general case, but my question is limited to modulo 2^32 and 2^64 arithmetic (unsigned 32-bit and 64-bit values). Also, maybe it can be done if we can add other cheap instructions like + and - in addition to * to emulate the right bit shift?

I assume exotic architecture where the right shift is more expensive than other arithmetic (similar to division).

uint64_t foo(uint64_t x) {
    return x >> 3; // how to avoid using right shift here?
}

There is a similar question How to perform right shifting binary multiplication? that asks how to replace multiplication of two unsigned numbers by right shift. Basically, it uses a loop internally. However, maybe if the second number is a constant, this loop can be avoided (or at least unrolled to a shorter fragment)?

Upvotes: 0

Views: 391

Answers (1)

user555045
user555045

Reputation: 64904

"Multiply-high" aka high-mul, hmul, mulh, etc, can be used to emulate a shift-right with a constant count. Usually that's not a good trade. It's also hardly related to C++.

Normal multiplication (putting floating point stuff aside) cannot be used to implement a shift-right.

my question is limited to modulo 2^32 and 2^64 arithmetic

It doesn't help. You can use that property to "unmultiply" (sort of like divide, except not really) by odd numbers, for example if b = 5 * a then a = b * 0xCCCCCCCD, using the modular multiplicative inverse. The number being inverted must be relatively-prime relative to the modulus. Since the modulus is a power of two, the "divisor" here cannot be a power of two (except 1, but that does nothing), so a shift-right cannot be done this way.

Another way to look at it (probably simpler), is that what a multiplication does is conditionally add together a bunch of left-shifted versions of the multiplicand. Only left-shift versions, not right-shifted versions. Which of those shifted versions are selected by the multiplier doesn't matter, there are no right-shifted versions to select.

Upvotes: 2

Related Questions