CODEWITHSUNDEEP
cbit-manipulationmultiplicationbit-shiftbit
user1596241
user1596241

Reputation:

Bitwise multiplication to achieve result

Is there a general set of rules to achieve a certain number by multiplying a known and unknown number. e.g. Suppose x = 13 and z = 9

Is there a way to find y such that 

    x * y = z     
=> 13 * y = 9

I don't want to utilize them as mathematical integers, but rather in terms of bits. So, I want to keep z an int. Obviously, there is an overflow in the bit representation, but I'm unsure how to find z without brute forcing all values in a 32-bit machine. I think y would be a very small number, negative.

Note: this isn't or a hw assignment, so you could change x and y to whatever, these are just examples.

Upvotes: 1

Views: 349

Answers (1)

user555045
user555045

Reputation: 64904

First, find the modular multiplicative inverse of x (13) mod 232. There are several ways to do it, many people will recommend the extended Euclidean algorithm, but it is not the simplest for this case. See Hacker's Delight chapter 10 (integer division by constants) for a simpler algorithm.

Anyway, once you know that the modular multiplicative inverse of 13 mod 232 is 0xc4ec4ec5, multiply that number by z to get y.

0xc4ec4ec5 * 9 = 0xec4ec4ed

So y = 0xec4ec4ed, and 0xec4ec4ed * 13 is indeed 9.

Note that if x is even, it has no inverse. If it's "at most as even as z" (that is, it has as many or fewer trailing zeroes than z) you can solve it this way after dividing out their highest common power of 2.

Upvotes: 5

Related Questions