How can I tell if a number is a multiple of four using only the logic operator AND?

Question

I'm messing with assembly language programming and I'm curious how I could tell if a number is a multiple of 4 using the logic operator AND?

I know how to do it using "div" or "remainder" instructions but I'm trying to do this with bit manipulation of number/word.

Can anyone point me in the right direction? I'm using MIPs but a Language agnostic answer is fine.

Answer 1

Well, to detect if a number is a multiple of another, you simple need to do x MOD y. If the result is 0, then it is an even multiple.

It is also true that for every y that is a power of 2, (x MOD y) is equivalent to (x AND (y - 1)).

Therefore:

IF (x AND 3) == 0 THEN
    /* multiple of 4 */

EDIT:

ok, you want to know why (x MOD y) == (x AND (y - 1)) when y is a power of 2. I'll do my best to explain.

Basically, if a number is a power of 2, then it has a single bit set (since binary is base 2). This means that all of the lower bits are unset. So for example: 16 == 10000b, 8 == 1000b, etc.

If you subtract 1 from any of these values. You end up with a the bit that was set being unset and all bits below it being set.

15 = 01111b, 7 = 0111b, etc. So basically it is creates a mask which can be used to test if the any of the lower bits were set. I hope that was clear.

EDIT: Bastien Léonard's comment covers it well too:

if you divide (unsigned) by 4, you shift two bits to the right. Thus the remainder is those two bits, which get lost when you divide. 4 - 1 = 11b, that is, a mask that yields the two rightmost bits when you AND it with a value.

EDIT: see this page for possibly clearer explanations: http://en.wikipedia.org/wiki/Power_of_two#Fast_algorithm_to_check_if_a_positive_number_is_a_power_of_two.

It covers detecting powers of 2 and using AND as a fast modulo operation if it is a power of 2.

Answer 2

(x & 3) == 0

W.r.t. assembly language, use TST if available, otherwise AND, and check the zero flag.

Answer 3

A number is a multiple of 4 if its lower 2 bits are 0, so you can simply shift the number right twice and check shifted bits for 0.

Answer 4

In x86 assembly:

    test eax, 3
    jnz not_multiple_of_4

    ; action to be taken if EAX is a multiple of 4

not_multiple_of_4:
    ; ...