CS 208 s21 — Programming With Bits

Table of Contents

1 bitwise operators

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.

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

1.1 bitwise AND

  • & represents bitwise AND
  • AND takes two bits and produces a 1 if both inputs are 1, otherwise it produces 0
  • A & B:
  1 1 1 0 1 0 0 1
& 0 1 0 1 0 1 0 1
  0 1 0 0 0 0 0 1

1.2 bitwise OR

  • | represents bitwise OR
  • OR takes two bits and produces a 1 if either inputs are 1, otherwise it produces 0
  • A | B:
  1 1 1 0 1 0 0 1
| 0 1 0 1 0 1 0 1
  1 1 1 1 1 1 0 1

1.3 bitwise XOR (eXclusive OR)

  • ^ represents bitwise XOR
  • XOR takes two bits and produces a 1 if either, but not both inputs are 1, otherwise it produces 0
  • A ^ B:
  1 1 1 0 1 0 0 1
​^ 0 1 0 1 0 1 0 1
  1 0 1 1 1 1 0 0

1.4 bitwise NOT

  • ~ represents bitwise NOT
  • NOT takes one bit and produces the inverse of its input (i.e., it flips the bit, 0 to 1 and 1 to 0)
  • ~B:
~ 0 1 0 1 0 1 0 1
  1 0 1 0 1 0 1 0

Bitwise NOT can be used to derive a formula for negation (additive inverse) in two's complement:

  • x + ~x = 0b11...11 (if we sum x and ~x we get a binary number that's all 1s since ~x has a 1 everywhere x has a 0 and vice versa)
  • x + ~x = -1 (all 1s represents -1 in two's complement for any width)
  • x + ~x + 1 = 0 (add 1 to both sides)
  • ~x + 1 = -x (subtract x from both sides—to get the additive inverse of a two's complement number, apply bitwise NOT and add 1)

2 bit shifting

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.

2.1 left shift

  • << represents left shift
  • left shift takes a bit vector and an integer \(n\) and shifts the bits \(n\) places to the left, filling in with zeros

left_shift.png

  • A<<1:
  1 1 1 0 1 0 0 1
1 1 1 0 1 0 0 1 _
_ 1 1 0 1 0 0 1 _
  1 1 0 1 0 0 1 0

2.2 right shift

  • >> represents right shift
  • right shift takes a bit vector and an integer \(n\) and shifts the bits \(n\) places to the right
    • a logical right shift fills in with zeros
    • a arithmetic right shift fills in with copies of the most significant bit

right_shift.png

  • A>>1 (logical):
  1 1 1 0 1 0 0 1  
  _ 1 1 1 0 1 0 0 1
  _ 1 1 1 0 1 0 0 _
  0 1 1 1 0 1 0 0  
  • A>>1 (arithmetic):
  1 1 1 0 1 0 0 1  
  _ 1 1 1 0 1 0 0 1
  _ 1 1 1 0 1 0 0 _
  1 1 1 1 0 1 0 0  

3 Boolean operators

C also provides logical operators for and, or, and not. These are written &&, ||, and ! in C. They treat 0 as representing false and any other value as representing true. They return either 0 or 1, indicating a logically false or true expression, respectively.

Expression Result
!0x41 0x00
0x55 && 0x00 0x00
0x55 || 0x00 0x01