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 =)

Resistor

Why don't you try a few example calculations by hand, then you'll see what happens. – Emporium

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.

Ashleeashleigh

This is only the case when all operands are positive! Depending on the language the behavior will differ. For instance in C, -5 % 4 == -1 despite the fact that in algebra we usually expect that -5 mod 4 is 3 (and in C: -5 & (4 - 1) == 3. This means for instance that a compiler will not optimize a literal % 4 with a & if the left operand is not unsigned. – Yousuf

@calandoa: We are discussing binary as a number system here, not bit-encoding of numbers. -5, for instance, is written -101. – Ashleeashleigh

@BlueRaja: Of course we are talking about bit encoding : & is not defined for mathematical -. I guess your remark is more "we are not talking about negative numbers". Maybe we are not, but this is not clear in the question nor in your answer, so I made it clearer. – Yousuf

Do you thing at something like number MOD 256 <=> (number & (0xFF00)) >> 8 (for 2^8 = 256) – Gerous

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

Gladisgladney

Answer 3

Consider when you take a number modulo 10. If you do that, you just get the last digit of the number.

  334 % 10 = 4
  12345 % 10 = 5

Likewise if you take a number modulo 100, you just get the last two digits.

  334 % 100 = 34
  12345 % 100 = 45

So you can get the modulo of a power of two by looking at its last digits in binary. That's the same as doing a bitwise and.

Irresponsible

Would that hold for powers of 2 as well ? 54 % 32 which is 2^5 gives 22. – Resistor

Popo: Yes. The number of bits at the end is determined by which power of two you're using. As described by Cicada, you would calculate it as 54 & (32-1). – Irresponsible

Answer 4

Modulo in general returns the remainder of a value after division. So x mod 4, for example, returns 0, 1, 2 or 3 depending on x. These possible values can be represented using two bits in binary (00, 01, 10, 11) - another way to do x mod 4 is to simply set all the bits to zero in x except the last two ones.

Example:

      x = 10101010110101110
x mod 4 = 00000000000000010

Lordosis

Answer 5

Answering your specific questions:

1. mod is a remainder operator. If applied to a series of numbers x in 0, 1, ..., then x mod n will be 0, 1, ..., n-1, 0, 1, ..., n-1, ad infinitum. When your modulus n is a power of 2, then x mod n will count up in binary from 0 to n-1, back to 0, to n-1, etc; for modulus n that looks like binary 01xxxxx, x mod n will cycle through every of those low-order bits xxxxx.
2. binary 1011000111011010 mod 1 is 0 (mod 2^0 yields the last zero bits; everything mod 1 is zero). binary 1011000111011010 mod binary 10000 is 1010 (mod 2^4 yields the last four bits).
3. Division and remainder of binary number by powers of two is particularly efficient because it's just shifting and masking; mathematically it's nothing special.
4. Example: See answer to question 2.

Karelian