CMPS-224 Homework 1: Binary Arithmetic and Bit Operations

Read Write Great Code, Vol 1, Ch 3 "Binary Arithmetic and Bit Operations" before starting this homework.

Resources:

Arithmetic Operations on Binary and Hexadecimal Numbers

WolframAlpha will convert to decimal. Just type the number in the search bar using the standard notation: 0x7af (hex), 11011b (binary), 0o373 (octal), where 0x denotes hex, 'b' denotes binary, and 0o denotes octal.

1. Perform these binary operations. Then convert the binary results into decimal.

          1011        1110       0111 0111        1100  
        + 1110      - 1011     + 0000 1011      - 0101
          ----        ----       ---------        ----

2. Perform these binary operations. Then convert the binary results into decimal.

           1010                 ________
         x 1001              11 | 10011   (include remainder)
           ----

3. Compute these bitwise logical operations. This is C syntax: '&' is bitwise AND; '|' is bitwise OR; '^' is bitwise XOR; '~' is NOT.

          11100       11010       11001   ~1     ~0     
        & 10101     | 10001     ^ 10010   --     --
          -----       -----       -----

4. Design a bitwise operation on bit string '101010' that will invert all the bits (i.e., flip 0 to 1 and 1 to 0). This computation is called the 1's complement.

5. Design a bitwise operation for any bit string of length 8 that will *mask* the first 4 bits (i.e. convert the first 4 bits to zeros). For example, on the bit string '1010 1011' you would end up with '0000 1011'.

6. Design a bitwise operation for any bit string that will invert the least significant (rightmost) bit and leave all other bits unchanged. E.g., 1010 1010 will become 1010 1011 and 1010 1011 will become 1010 1010.

7. For what integer values of num is this C condition true?

           ((num  & 1) != 0)

8. For what integer values of num is this C condition true?

           ((num & 15) == 0)

9. Convert the following binary, decimal or octal numbers into hexadecimal (base 16).

       1010 1110 1001 1100 (binary to hex)
       11 1001 (binary to hex)
       31 (decimal to hex)
       67 (octal to hex)

10. Assume you want to compare bits 0, 6, 17 and 31 of two 32-bit strings, where the bit at position zero is the least significant bit. One way to do this is to AND each string with a mask that will keep the bits you want to compare and change all other bits to 0. If the resulting integers are equal, then the bits are all the same. What mask do you need? Give your answer in hex.

11. Use your mask from question #10 to verify that bits 0, 6, 17 and 31 in these two strings do in fact match:

          1100 1010 0011 1001 1110 0000 1111 1100    
          1000 0110 0001 0000 1111 1010 0101 1010

12. Perform the following conversions.

           2357 (decimal to binary) 
           1011 1110 (binary to decimal)
           347 (octal to decimal) 
           A1E (hex to decimal)

13. Translate -3 (decimal) into its binary representation in two's complement. Assume your machine stores an integer in 8 bits, with bit 7 (the leftmost bit) as the sign bit where 0 denotes a positive integer; e.g., this is 3:

        0000 0011

Check your work by adding -3 and 3 (you should get all zeros).

14. Modulo (mod or %) is an operation on the set of integers such that m mod n = m if m < n otherwise m mod n is the remainder of m / n. Examples:

          (7 mod 9) = 7. (7 mod 3) = 1. (7 mod 7) = 0. (63 mod 9) = 0. 
          (7 mod 4) = 3. (21 mod 4) = 1.

Create a modulo-n counter for n = 16 using only a bitwise AND operation. i.e., construct an operation M(x) that will take any integer x and only return values y = 0..15. M is also counter, thus if M(x) = 15 then M(x+1) = 0. For all other values x, if M(x) = y, M(x+1) = y + 1. Test that your counter is working by applying x = 0, 15, 16 and 17. In modulo-16 the results should be M(0) = 0; M(15) = 15; M(16) = 0; M(17) = 1. Note: there is an error in WCG, Ch.3 pg.52. The note at the top of the page should read:

      Note: 0x1f = 31 = 2^5 - 1, so n = 32 and m = 5.

15. The syntax for C's shift logical left and shift logical right bit operations is:

   E1 << 2 is E1 left-shifted 2 bits; vacated bits are filled with zeros
   E1 >> 2 is E1 right-shifted 2 bits; vacated bits are filled with zeros

What does this C function accomplish and what is the purpose of m?

      unsigned int n = 176;  //unsigned int holds a positive integer in 32 bits
      unsigned int m = 1 << 31;
      while (m) {
        char c = (n & m) ? '1' : '0';
        write(1,c,1);        // write one character to standard out
        m = m >> 1;
      }

16. What is the decimal value of m after this shift logical left operation?

       unsigned int m = 21;
       m << 2;   # the 2 means shift left by 2 bits

17. What is the decimal value of m after these right shift operation? Assume integer division so the remainder is lost.

       unsigned int m = 64;
       m >> 2;   # shift right 2 bits 
       unsigned int m = 9;
       m >> 3;  # shift right 3 bits

18. What is the decimal value of m after this left shift operation if negative integers are stored in 8 bits and two's complement?

       int m = -5;
       m << 1;

19. What is the decimal value of m after this right shift operation if negative integers are stored in 8 bits and two's complement?

      int m = -8;
      m >> 1;