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?


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$$

  • $\begingroup$ Wow, thanks, I think I'm just fatigued after doing the assignment for so long. Do you have any tips for visualising better on numerical properties in terms of binary? Like practice question or notes recommendations? $\endgroup$ – Prashin Jeevaganth Sep 19 '18 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.