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

phuclv
  • 37,963
  • 15
  • 156
  • 475
Zo Has
  • 12,599
  • 22
  • 87
  • 149

5 Answers5

84

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.

BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
  • 4
    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. – calandoa Nov 18 '16 at 15:46
  • 1
    @calandoa: We are discussing binary as a number system here, not bit-encoding of numbers. `-5`, for instance, is written `-101`. – BlueRaja - Danny Pflughoeft Nov 18 '16 at 16:08
  • @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. – calandoa Nov 22 '16 at 11:18
  • Do you thing at something like `number MOD 256` <=> `(number & (0xFF00)) >> 8` (for 2^8 = 256) – Sandburg Nov 26 '19 at 15:29
45

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
user703016
  • 37,307
  • 8
  • 87
  • 112
17

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.

Brian
  • 2,511
  • 20
  • 26
  • Would that hold for powers of 2 as well ? 54 % 32 which is 2^5 gives 22. – Zo Has Jul 12 '11 at 21:07
  • 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). – Brian Jul 12 '11 at 21:39
6

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
Antti
  • 11,944
  • 2
  • 24
  • 29
4

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.
Liudvikas Bukys
  • 5,790
  • 3
  • 25
  • 36