Recitation 04: Bitwise Operations
- A few more borrowed slides from 15-213.
- Masking: using bitwise operations to manipulate certain bits.
- &: forces bits to 0. Ex. 10011101 & 00000111 = 00000101
forces the leading 5 bits to 0 and preserves the last 3 bits.
- |: forces bits to 1. Ex. 10011101 | 11111000 = 11111101 forces the
leading 5 bits to 1 and preserves the last 3 bits
- ^: selectively flips bits. Ex. 10011101 ^ 00111100 = 10100001 flips
the middle 4 bits.
- <<: Left shifting shifts the bits "to the left." Extra bits on
the left are discarded and extra bits on the right are filled in
with zeros. Ex. 10011101 << 4 = 11010000.
- >>: Right shifting shifts the bits "to the right." Extra bits
on the right are discarded and extra bits on the left are filled in my
copying the most significant bit in the original. Ex. 10011101 >>
4 = 11111101.
- After testing a few examples, it seems like shifting is effectively
like multiplying and dividing by 2. Does this always hold?
- Combining bitwise ops: We can combine what is shown above to do some
more advanced operations. For example, say we want to determine the
value of the most significant bit (assuming only 8 bits): (11011101
>> 7) & 00000001 = 1.
- How does working with arrays affect the contracts we write?
- Challenge: suppose I want to write the maskint(int n, int s)
that sets the lowest $s$ bits of $n$ to 1. Try to do this using only
bitwise operations, and not any loops, etc. maskint.c0 [maskint-sol.c0]
If you have any comments or see any errors, please
let me know.