Bitwise Arithmetics

We can extend Boolean operations to also operate on bit vectors (binary strings). If a is a bit vector, and b is a bit vector - we define a & b to also be a bit vector, where the i-th element equals ai & bi. Links: how bitwise operators work in Js, modular arithmetic on khan academy Related courses: Boolean Algebra - memcode.com/courses/138, Converting number bases - memcode.com/courses/127

16 flashcards · Computer Science · by lakesare

  1. Solve: 0110 xor 1100 ~1110

    0110 xor 1100 = 1010 ~1110 = 0001

  2. do_something_with(0x87654321) = 0x00000021 Keep the least significant byte of x, with all other bits set to 0.

    1. 0x87654321 & 0xFF = 0x00000021 & operator turns all operands into 32-bit binary strings. 2. 0x87654321 mod 162 = 33 = 0x00000021

  3. do_something_with(0x87654321) = 0x876543FF The least significant byte set to all 1s, and all other bytes of x left unchanged.

    0x87654321 | 0xFF = 0x876543FF Least significant byte of 0x87654321 is 21.

  4. Evaluate: ~0x5 for 32-bit integer.

    ~0x5 = ~516 = ~1012 = (but it's stored in, e.g., 32 bits, so) ~00000000 00000000 00000000 000001012 = 11111111 11111111 11111111 111110102 = 0xFF FF FF FA.

  5. How do bitwise operators work?

    The operands are converted to 32-bit integers and then converted to base 2 Each bit in the first operand is paired with the corresponding bit in the second operand: first bit to first bit, second bit to second bit, and so on The operator is applied to each pair of bits, and the result is constructed bitwise.

  6. What does left shift x << k do?

    x is shifted k bits to the left, dropping off the k most significant bits and filling the right end with k zeros.

  7. What does right shift x >> k do?

    There are 2 types of right shifts - logical and arithmetic. logical: drop k least significant digits, fills the left end with k zeros. arithmetic: drop k least significant digits, fills the left end with k repetitions of the most significant bit. This convention might seem peculiar, but it is useful for operating on signed integer data.

  8. Solve for 2 values of x argument:

  9. Name shift operators in Java and Js.

    x << k (left shift) x >> k (right shift - arithmetic) x >>> k (right shift - logical) --- analogous to the left shift

  10. What's bit masking?

    It's an operation of setting some bits of a bit string to 0s, 1s, or flipping them.

  11. We have the variable a = 0b10111011. Use a bitmask to achieve a result where the third bit from the right of a is turned on.

    a = 0b10111011 bitmask = 0b100 a | bitmask //=> 0b10111111

  12. We have the variable a = 0b11101110. Use a bitmask to achieve a result where all bits in a are flipped.

    a = 0b11101110 bitmask = 0b11111111 a xor bitmask //=> 0b10001

  13. Extract second most significant byte of 11111001 11101111 11111111 11111010.

    1. shift 11111001 11101111 11111111 11111010 >>> 16 2. mask 00000000 00000000 11111001 11101111 & 11111111 00000000 00000000 00000000 11101111

  14. Register A holds 4-bit binary number 1000. Determine B operand and the logic micro-operation to be performed in order to change the value in A to 0101.

    1000 xor 1101 = 0101.

  15. Name 2 symbols used for denoting XOR.

    ⊕ (used in algebraic expressions) ^ (used in C, Java and Js)

  16. Insert operand and operation needed to extract last 4 digits: 101110101010 _ ___________ = 1010

    101110101010 % 24 = 1010 (2986 % 16 = 10) Just like 763 % 102 = 63.