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.
• Shifting
  • <<: 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?
  • Returning an array of the first $n$ fibonacci numbers. fib.c0 [fib-sol.c0]
  • Ways to catch out of bounds access. bounds.c0 [bounds-sol.c0]
• 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.