Mod of power 2 on bitwise operators?
- How does mod of power of 2 work on only lower order bits of a binary number (
1011000111011010
)? - What is this number mod 2 to power 0, 2 to power 4?
- What does power of 2 have to do with the modulo operator? Does it hold a special property?
- 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 =)
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.
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
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.
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
Answering your specific questions:
- 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.
- 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).
- 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.
- Example: See answer to question 2.
精彩评论