Mod of power 2 on bitwise operators?

Question

1. How does mod of power of 2 work on only lower order bits of a binary number (1011000111011010)?
2. What is this number mod 2 to power 0, 2 to power 4?
3. What does power of 2 have to do with the modulo operator? Does it hold a special property?
4. Can someone give me an example?

The instructor says "When you take something mod to power of 2 you just take its lower order bits". I was too afraid to ask what he meant =)

Answer 1

He meant that taking number mod 2^n is equivalent to stripping off all but the n lowest-order (right-most) bits of number.

For example, if n == 2,

number      number mod 4 00000001      00000001 00000010      00000010 00000011      00000011 00000100      00000000 00000101      00000001 00000110      00000010 00000111      00000011 00001000      00000000 00001001      00000001 etc. 

So in other words, number mod 4 is the same as number & 00000011 (where & means bitwise-and)

---

Note that this works exactly the same in base-10: number mod 10 gives you the last digit of the number in base-10, number mod 100 gives you the last two digits, etc.

Answer 2

What he means is that :

x modulo y = (x & (y − 1)) 

When y is a power of 2.

Example:

0110010110 (406) modulo 0001000000 (64)  = 0000010110 (22) ^^^^<- ignore these bits 

Using your example now :

1011000111011010 (45530) modulo 0000000000000001 (2 power 0) = 0000000000000000 (0) ^^^^^^^^^^^^^^^^<- ignore these bits  1011000111011010 (45530) modulo 0000000000010000 (2 power 4) = 0000000000001010 (10) ^^^^^^^^^^^^<- ignore these bits