Bitwise Math

00:00 In the previous lesson, I showed you the ons and offs of binary numbers. In this lesson, I’ll be talking about operations on binary values.

00:10 Bitwise operations affect one or more bits in a binary value. The most common bitwise operations are AND, OR, XOR, NOT, and shifts.

00:24 Bitwise AND, noted as a single ampersand (&) in most programming languages, combines two binary values into a result. Each bit in the values being combined is compared. If they’re both 0, the resulting value is 0. If either of them is 1, then the resulting value is still 0. And if they’re both 1, the result is 1. Bitwise operations can be expressed using something called a truth table.

00:55 The header row and header column contain the values of bits being compared and their intersection in the table shows the result. So, 00 in the blue meet to form 0 in the gray, 11 in the blue meet to form 1 in the gray, and the mixed values in between. Consider the following example.

01:18 1001 1100 AND-ed with 0011 0100. Line up the 1s, and any position with a 1 in both values results in a 1. Everything else results in a 0.

01:37 Bitwise OR, noted as a single pipe symbol in most programming languages, combines two binary values. Each bit is compared, and if either of them is on, the resulting value has the corresponding bit on. 0 OR 0 is 0, 1 OR 0 is 1, 0 OR 1 is 1, and 1 OR 1 is also 1.

02:04 Here’s the corresponding truth table. And using the same numbers from before, anywhere there is a 1 in either number results in a 1 in the outcome.

02:17 Bitwise XOR, also known as exclusive OR, is usually a caret (^) in most programming languages. Exclusive OR is like bitwise OR, except both values being 1 results in 0.

02:30 Only one of the bits can be on, exclusively. 0 XOR 0 is 0, 1 XOR 0 is 1, 0 XOR 1 is 1, and the exclusive part, 1 XOR 1, is 0. Here’s the corresponding truth table,

02:52 and an example. Follow the 1s, but only if they cross a 0. There’s the result.

03:02 Up until now, all the bitwise operations you’ve seen have operated on two values. The NOT is different. It is a unary operation. Bitwise NOT is usually the tilde symbol (~) in most programming languages and is responsible for inverting each bit in a binary number.

03:19 So 0 becomes 1, and 1 becomes 0. Going through an example, everything flips to the other case.

03:31 There are two bitwise shift operators, one for shifting left and one for shifting right. These are usually denoted as double less than (<<) and double greater than (>>) in most programming languages.

03:42 Each shift operation includes a parameter: a number that indicates how many positions the bits are going to shift. The following examples are a bit messy, as they combine both binary and decimal numbers.

03:55 Note the subscript next to each number. Subscript 2 means binary, or base-2, while subscript 10 means decimal, or base-10. 1 shifted left by one position gives 10 binary, decimal 2.

04:10 1 shifted by two positions gives 100 binary, or decimal 4. Note that the new digits shifted into the lowest positions are all 0s. 100 shifted right by one position gives 10. The rightmost digit of the original is chopped off.

04:31 100 shifted right by two positions gives 1. Because each digit in binary represents a power of 2, shifting left and right are the equivalent of multiplying and dividing by 2.

04:45 This is like multiplying and dividing by 10 in decimal. Just add or remove a digit. 0 shifted left is still 0, and likewise, 0 shifted right is also still 0.

04:58 Here’s a trusty example with a left shift. Digits move left, and 0s come in on the right-hand side. And now here’s the right shift.

05:11 The rightmost digits get chopped off.

05:16 So far, everything I’ve been talking about is theory. As is often the case, practice is a bit messier than theory. Computers use binary values to represent numbers.

05:26 The problem is computers have limited space to store things, and that limitation has an effect on bitwise math. Consider an eight-digit binary number being stored in a place with enough space for eight digits.

05:38 What happens when you shift this left? Well, you can’t put a nine-digit number in an eight-digit space. Complications ensue. This means bitwise manipulation of binary values may not have the effect you may think it does, depending on the programming language and the data type within the language that you’re using. In theory land, everything so far has been an unsigned number—that means everything is zero or more—and all operations were logical.

06:06 That means the bits are played with with no consideration for what they are representing. These two assumptions are handled differently in different programming languages.

06:17 Some languages even have the behavior change based on the data type being used. Did you notice the slide’s title? If you’re not familiar with the phrase, it’s Latin for buyer beware. As a purveyor of the Python programming paradigm, you may find everything isn’t peachy.

06:33 Those two assumptions I just stated about theory land? Neither of them apply to the practice of Python. Python’s integer isn’t unsigned. It can store negative values.

06:44 The way the negative values are stored impacts the second assumption about bitwise logical operations as well.

06:53 Next up, I’ll show you how that last sentence I just uttered will make your life complicated.