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

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.

From stackoverflow

• 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.

  : um, his answer does use bit manipulation, look at the whole answer...

  Mithrax : @ilproxyil, his answer has been edited since I commented.

  Evan Teran : Yea, i was explaining why you can AND with y -1, to get the same value as MOD y.

  Evan Teran : @tvanfosson: thanks for the rollback, was about to do that myself after your comment in the other post :).

  Mithrax : @Evan Teran, I see how you say that they are equivalent but I still don't see why it would be y - 1?

  Bastien Léonard : @Mithrax: 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.

  Evan Teran : @Bastien: goo way to word it, added to my answer.

  Simucal : Thanks Evan and everyone else. I appreciate it.

  Derek E : Write x as an expansion in powers of 2 and assume y = 2^k for some k. Then write: x = (\Sigma_{m=k}^{\infty} c_m * 2^m) + Remainder. The first term is a multiple of y, while 'Remainder' < y. So, x mod y is equivalent to 'Remainder'. But this is just the bit pattern x & y-1.

• (x & 3) == 0

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

  Mithrax : Why is it 3 again?

  starblue : @John Millikin That's wrong, 0 is a multiple of any number.

  tvanfosson : @John -- yes it is 0 is the product of 0 x 4. http://en.wikipedia.org/wiki/Multiple_(mathematics)

  John Millikin : My mistake -- not thinking clearly, obviously.

• 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.

• 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:
      ; ...