CS 208 s20 — Programming With Bits

A bitwise operator is a mathematical operator the works at the level of bits. In particular these operators act on each bit of the input separately. These operations closely resemble the actual circuitry that make up computer components. Those circuits take in one or two electrical signals at either a high (1) or low (0) voltage, and output a high or low voltage (a 1 or a 0).

This correspondence between circuitry and these operators often makes them fast and/or more power efficient than standard arithmetic operations. Thus, compilers tend to use them in place of standard arithmetic when possible.

These operations are also essential in settings with very little memory. Since storage sizes are fixed, like a 4-byte integer, representing 1-bit of information like true/false (1 or 0) will leave a lot of space unused. To be more efficient, we might want to combine a bunch of values into the bits of an int, with each value using a different range of the 32 bits. We would need ways of combining and extracting these values, however, and that's where bitwise operators come in.

To demonstrate these different operations, we'll define two bit vectors A and B each 8 bits long. A bit vector (also called a bit array or bit string) is a string of zeros and ones of some fixed length.

• A = 11101001
• B = 01010101

Bit shift operators are slightly different from the four bitwise operators we've looked at so far. Instead of operating on each individual bit or pair of bits in place, they slide the bits \(n\) places to the left or right.

• in C, these operators can apply to any integral data type
  • 1-byte (char) examples (verify you understand how these work):²
    • ~0x41
    • ~0x00
    • 0x68 & 0x55
    • 0x68 | 0x55
    • 0x34<<1
    • 0x68>>2
    • how many bits are in each of these results?
      • all of them contain 8 bits (1 byte)! zeroes used to "fill out" the fixed length

Returning to the idea of combining multiple values into a single quantity, let's say we want to store three 1-byte characters in a 4-byte integer. The code below shows how these quantities would be combined and extracted. See it in C tutor here. All the types are unsigned to prevent C from performing sign extension when converting a char to an int.

#include <stdio.h>

int combine(unsigned char a, unsigned char b, unsigned char c) {
    unsigned result = a; // result has a in the low order byte, 0 in the rest
    printf("result = %x\n", result);
    result = (result<<8) | b; // shift a 1 byte to the left, use OR to put b in the low order byte
    printf("result = %x\n", result);
    result = (result<<8) | c; // shift a and b 1 byte to the left, use OR to put c in the low order byte    
    printf("result = %x\n", result);
    return result;
}

int main() {
    unsigned char a = 0xaa;
    unsigned char b = 0xbb;
    unsigned char c = 0xcc;
    unsigned x = combine(a, b, c);

    // use the shift-and-mask strategy to extract each char
    // masking means use AND to zero-out bits you don't care about, leaving only the ones you do
    printf("a = %x\n", (x>>16) & 0xff); // shift x to the right to put a in low byte, mask out the rest with AND
    printf("b = %x\n", (x>>8) & 0xff); // shift x to the right to put b in low byte, mask out the rest with AND
    printf("c = %x\n", x & 0xff); // c is already in the low byte, mask out the rest with AND
}    

QUICK CHECK: write a C expression to extract most significant byte from a 32-bit integer³. For example, given x = 0b 01100001 01100010 01100011 01100100 (spaces added to separate bytes), should return 0b 00000000 00000000 00000000 01100001

C also provides the Boolean logic operators (and, or, not) that you're probably familiar with from other programming languages. Read section 2.1.8 from the CSPP book (p. 56-57) to get acquainted with these.

1. CSPP practice problems 2.12 (p. 55), 2.14 (p. 57), 2.15 (p. 57), and 2.16 (p. 58)
2. Take the Week 2 quiz on Moodle. You must complete it by 9pm Wednesday, April 22
3. Remember lab 0 is due 9pm Monday, April 20