How to get the operand for the bitwise operator of finding remainder

Question

Sorry if this sounds offtopic, but I will try to phrase the problem in such a way till it’s an arithmetic problem.

As part of a hardware MIPS assembly assignment, I have to find the mask for the andi instruction to compute the remainder, R of a number, N as a result of division by a divisor X, using bitwise operators, given that X is definitely some power of 2 (R= N%X) From my inference of how to find the suitable mask, these numbers’ binary form will start with 1, followed by a number of trailing zeroes equal to the power 2 is raised by. The mask will be the 1s-complement of this divisor.

Example will be find the remainder when 12 is divided by 8: $12=(1100)_{2}$ and $8=(1000)_{2}$, and taking 1s complement of $(1000)_{2}$ will be $$(0111)_{2}$$ which will give us the correct remainder of $(100)_{2}= 4$ when the AND operator is applied.

While I know that the solution is just a number of trailing 1’s, I do not know what bitwise operation(and,or,xor,nor) can be done on the original number to somehow isolate the numbers to the left of the significant digit of the original divisor.

For example, if divisor is $2=(0010)_{2}$, and I intend to xor it with $(1111)_{2}$, I will get $(1101)_{2}$, but in reality I only want $(0001)_{2}$ as a result for getting the mask.

Can anyone suggest an appropriate solution to my problem?

Answer 1

It sounds like you're asking how to find the mask $M$ for the andi instruction given the divisor $X$, given that $X$ is a power of 2? Is that right? And it looks like you already know that once we find the mask $M$, the remainder $R$ is $N \& M$, where $\&$ is the bitwise "and" operator.

Subtracting $1$ will do the trick: $M = X - 1$. For example:

$$X = (0001)_2 \qquad M = (0001)_2 - 1 = (0000)_2$$ $$X = (0010)_2 \qquad M = (0010)_2 - 1 = (0001)_2$$ $$X = (0100)_2 \qquad M = (0100)_2 - 1 = (0011)_2$$ $$X = (1000)_2 \qquad M = (1000)_2 - 1 = (0111)_2$$