alexander/intro-to-python
1
1
Fork 0
Code Issues Pull requests Releases Activity
intro-to-python/05_numbers/00_content.ipynb
Alexander Hess 94e5112f10
Release 0.1.0 
After refurbishing the project we prepare a new relaease.
There are no changes with respect to the contents as compared to v0.0.0
that are noteworthy release notes.
2024-04-08 22:13:31 +02:00

2454 lines
58 KiB
Text
Raw Permalink Blame History

{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"**Note**: Click on \"*Kernel*\" > \"*Restart Kernel and Clear All Outputs*\" in [JupyterLab](https://jupyterlab.readthedocs.io/en/stable/) *before* reading this notebook to reset its output. If you cannot run this file on your machine, you may want to open it [in the cloud <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_mb.png\">](https://mybinder.org/v2/gh/webartifex/intro-to-python/main?urlpath=lab/tree/05_numbers/00_content.ipynb)."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Chapter 5: Numbers & Bits"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"After learning about the basic building blocks of expressing and structuring the business logic in programs, we focus our attention on the **data types** Python offers us, both built-in and available via the [standard library <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/index.html) or third-party packages.\n",
"\n",
"We start with the \"simple\" ones: Numeric types in this chapter and textual data in [Chapter 6 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/06_text/00_content.ipynb). An important fact that holds for all objects of these types is that they are **immutable**. To reuse the bag analogy from [Chapter 1 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/01_elements/00_content.ipynb#Objects-vs.-Types-vs.-Values), this means that the $0$s and $1$s making up an object's *value* cannot be changed once the bag is created in memory, implying that any operation with or method on the object creates a *new* object in a *different* memory location.\n",
"\n",
"[Chapter 7 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/07_sequences/00_content.ipynb), [Chapter 8 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/08_mfr/00_content.ipynb), [Chapter 9 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/09_mappings/00_content.ipynb), [Chapter 10 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/10_arrarys/00_content.ipynb) then cover the more \"complex\" data types, including, for example, the `list` type. Finally, [Chapter 11 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/11_classes/00_content.ipynb) completes the picture by introducing language constructs to create custom types.\n",
"\n",
"We have already seen many hints indicating that numbers are not as trivial to work with as it seems at first sight:\n",
"\n",
"- [Chapter 1 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/01_elements/00_content.ipynb#%28Data%29-Type-%2F-%22Behavior%22) reveals that numbers may come in *different* data types (i.e., `int` vs. `float` so far),\n",
"- [Chapter 3 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/03_conditionals/00_content.ipynb#Boolean-Expressions) raises questions regarding the **limited precision** of `float` numbers (e.g., `42 == 42.000000000000001` evaluates to `True`), and\n",
"- [Chapter 4 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/04_iteration/00_content.ipynb#Infinite-Recursion) shows that sometimes a `float` \"walks\" and \"quacks\" like an `int`, whereas the reverse is true in other cases.\n",
"\n",
"This chapter introduces all the [built-in numeric types <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/stdtypes.html#numeric-types-int-float-complex): `int`, `float`, and `complex`. To mitigate the limited precision of floating-point numbers, we also add an [Appendix <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/05_numbers/03_appendix.ipynb) where we look at two replacements for the `float` type in the [standard library <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/index.html), namely the `Decimal` type in the [decimals <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/decimal.html#decimal.Decimal) and the `Fraction` type in the [fractions <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/fractions.html#fractions.Fraction) module."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## The `int` Type"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The simplest numeric type is the `int` type: It behaves like an [integer in ordinary math <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Integer) (i.e., the set $\\mathbb{Z}$) and supports operators in the way we saw in the section on arithmetic operators in [Chapter 1 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/01_elements/00_content.ipynb#%28Arithmetic%29-Operators).\n",
"\n",
"One way to create `int` objects is by simply writing its value as a literal with the digits `0` to `9`."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"a = 42"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Just like any other object, the `42` has an identity, a type, and a value."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"94857615440928"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"id(a)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"int"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"type(a)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"42"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"A nice feature in newer Python versions is using underscores `_` as (thousands) separators in numeric literals. For example, `1_000_000` evaluates to `1000000` in memory; the `_`s are ignored by the interpreter."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"1000000"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"1_000_000"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"We may place the `_`s anywhere we want."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"123456789"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"1_2_3_4_5_6_7_8_9"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"It is syntactically invalid to write out leading `0`s in numeric literals. The reason for that will become apparent in the next section."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"ename": "SyntaxError",
"evalue": "leading zeros in decimal integer literals are not permitted; use an 0o prefix for octal integers (1481240458.py, line 1)",
"output_type": "error",
"traceback": [
"\u001b[0;36m Cell \u001b[0;32mIn[7], line 1\u001b[0;36m\u001b[0m\n\u001b[0;31m 042\u001b[0m\n\u001b[0m ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m leading zeros in decimal integer literals are not permitted; use an 0o prefix for octal integers\n"
]
}
],
"source": [
"042"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Another way to create `int` objects is with the [int() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/functions.html#int) built-in that casts `float` or properly formatted `str` objects as integers. Then, decimals are truncated (i.e., \"cut off\")."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"42"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"int(42.11)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"42"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"int(42.87)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Whereas the integer division operator `//` \"rounds\" towards negative infinity (cf., the \"*(Arithmetic) Operators*\" section in [Chapter 1 <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/01_elements/00_content.ipynb#%28Arithmetic%29-Operators)), the [int() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/functions.html#int) built-in rounds towards `0`."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"-42"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"int(-42.87)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"When casting `str` objects as `int`s, the [int() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/functions.html#int) built-in is less forgiving. We must not include any decimals as shown by the `ValueError`. Yet, leading and trailing whitespace is gracefully ignored."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"42"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"int(\"42\")"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"ename": "ValueError",
"evalue": "invalid literal for int() with base 10: '42.0'",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mValueError\u001b[0m Traceback (most recent call last)",
"Cell \u001b[0;32mIn[12], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[38;5;28;43mint\u001b[39;49m\u001b[43m(\u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43m42.0\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m)\u001b[49m\n",
"\u001b[0;31mValueError\u001b[0m: invalid literal for int() with base 10: '42.0'"
]
}
],
"source": [
"int(\"42.0\")"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"42"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"int(\" 42 \")"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The `int` type follows all rules we know from math, apart from one exception: Whereas mathematicians to this day argue what the term $0^0$ means (cf., this [article <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Zero_to_the_power_of_zero)), programmers are pragmatic about this and simply define $0^0 = 1$."
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"0 ** 0"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Binary Representations"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"As computers can only store $0$s and $1$s, `int` objects are nothing but that in memory as well. Consequently, computer scientists and engineers developed conventions as to how $0$s and $1$s are \"translated\" into integers, and one such convention is the **[binary representation <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Binary_number)** of **non-negative integers**. Consider the integers from $0$ through $255$ that are encoded into $0$s and $1$s with the help of this table:"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"|Bit $i$| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |\n",
"|:------|:----|:----|:----|:----|:----|:----|:----|:----|\n",
"| Digit |$2^7$|$2^6$|$2^5$|$2^4$|$2^3$|$2^2$|$2^1$|$2^0$|\n",
"| $=$ |$128$| $64$| $32$| $16$| $8$ | $4$ | $2$ | $1$ |"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"A number consists of exactly eight $0$s and $1$s that are read from right to left and referred to as the **bits** of the number. Each bit represents a distinct multiple of $2$, the **digit**. For sure, we start counting at $0$ again.\n",
"\n",
"To encode the integer $3$, for example, we need to find a combination of $0$s and $1$s such that the sum of digits marked with a $1$ is equal to the number we want to encode. In the example, we set all bits to $0$ except for the first ($i=0$) and second ($i=1$) as $2^0 + 2^1 = 1 + 2 = 3$. So the binary representation of $3$ is $00~00~00~11$. To borrow some terminology from linear algebra, the $3$ is a linear combination of the digits where the coefficients are either $0$ or $1$: $3 = 0*128 + 0*64 + 0*32 + 0*16 + 0*8 + 0*4 + 1*2 + 1*1$. It is *guaranteed* that there is exactly *one* such combination for each number between $0$ and $255$.\n",
"\n",
"As each bit in the binary representation is one of two values, we say that this representation has a base of $2$. Often, the base is indicated with a subscript to avoid confusion. For example, we write $3_{10} = 00000011_2$ or $3_{10} = 11_2$ for short omitting leading $0$s. A subscript of $10$ implies a decimal number as we know it from elementary school.\n",
"\n",
"We use the built-in [bin() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/functions.html#bin) function to obtain an `int` object's binary representation: It returns a `str` object starting with `\"0b\"` indicating the binary format and as many $0$s and $1$s as are necessary to encode the integer omitting leading $0$s."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b11'"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(3)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"We may pass a `str` object formatted this way as the argument to the [int() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/functions.html#int) built-in, together with `base=2`, to create an `int` object, for example, with the value of `3`."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"int(\"0b11\", base=2)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Moreover, we may also use the contents of the returned `str` object as a **literal** instead: Just like we type, for example, `3` without quotes (i.e., \"literally\") into a code cell to create the `int` object `3`, we may type `0b11` to obtain an `int` object with the same value."
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"0b11"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Another example is the integer `123` that is the sum of $64 + 32 + 16 + 8 + 2 + 1$: Thus, its binary representation is the sequence of bits $01~11~10~11$, or to use our new notation, $123_{10} = 1111011_2$."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b1111011'"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(123)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Analogous to typing `123` into a code cell, we may write `0b1111011`, or `0b_111_1011` to make use of the underscores, and create an `int` object with the value `123`."
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"123"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"0b_111_1011"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"`0` and `255` are the edge cases where we set all the bits to either $0$ or $1$."
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b0'"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(0)"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b1'"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(1)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b10'"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(2)"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b11111111'"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(255)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Groups of eight bits are also called a **byte**. As a byte can only represent non-negative integers up to $255$, the table above is extended conceptually with greater digits to the left to model integers beyond $255$. The memory management needed to implement this is built into Python, and we do not need to worry about it.\n",
"\n",
"For example, `789` is encoded with ten bits and $789_{10} = 1100010101_2$."
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b1100010101'"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(789)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"To contrast this bits encoding with the familiar decimal system, we show an equivalent table with powers of $10$ as the digits:\n",
"\n",
"|Decimal| 3 | 2 | 1 | 0 |\n",
"|-------|------|------|------|------|\n",
"| Digit |$10^3$|$10^2$|$10^1$|$10^0$|\n",
"| $=$ |$1000$| $100$| $10$ | $1$ |\n",
"\n",
"Now, an integer is a linear combination of the digits where the coefficients are one of *ten* values, and the base is now $10$. For example, the number $123$ can be expressed as $0*1000 + 1*100 + 2*10 + 3*1$. So, the binary representation follows the same logic as the decimal system taught in elementary school. The decimal system is intuitive to us humans, mostly as we learn to count with our *ten* fingers. The $0$s and $1$s in a computer's memory are therefore no rocket science; they only feel unintuitive for a beginner."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"### Arithmetic with Bits"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Adding two numbers in their binary representations is straightforward and works just like we all learned addition in elementary school. Going from right to left, we add the individual digits, and ..."
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"1 + 2"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b1 + 0b10 = 0b11'"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(1) + \" + \" + bin(2) + \" = \" + bin(3)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"... if any two digits add up to $2$, the resulting digit is $0$ and a $1$ carries over."
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"1 + 3"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b1 + 0b11 = 0b100'"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(1) + \" + \" + bin(3) + \" = \" + bin(4)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Multiplication is also quite easy. All we need to do is to multiply the left operand by all digits of the right operand separately and then add up the individual products, just like in elementary school."
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"12"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"4 * 3"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b100 * 0b11 = 0b1100'"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(4) + \" * \" + bin(3) + \" = \" + bin(12)"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b100 * 0b1 = 0b100'"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(4) + \" * \" + bin(1) + \" = \" + bin(4) # multiply with first digit"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b100 * 0b10 = 0b1000'"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(4) + \" * \" + bin(2) + \" = \" + bin(8) # multiply with second digit"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The [Further Resources <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/05_numbers/06_resources.ipynb) section at the end of this chapter provides video tutorials on addition and multiplication in binary. Subtraction and division are a bit more involved but essentially also easy to understand."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Hexadecimal Representations"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"While in the binary and decimal systems there are two and ten distinct coefficients per digit, another convenient representation, the **hexadecimal representation**, uses a base of $16$. It is convenient as one digit stores the same amount of information as *four* bits and the binary representation quickly becomes unreadable for larger numbers. The letters \"a\" through \"f\" are used as digits \"10\" through \"15\".\n",
"\n",
"The following table summarizes the relationship between the three systems:"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"|Decimal|Hexadecimal|Binary|$~~~~~~$|Decimal|Hexadecimal|Binary|$~~~~~~$|Decimal|Hexadecimal|Binary|$~~~~~~$|...|\n",
"|-------|-----------|------|--------|-------|-----------|------|--------|-------|-----------|------|--------|---|\n",
"| 0 | 0 | 0000 |$~~~~~~$| 16 | 10 | 10000|$~~~~~~$| 32 | 20 |100000|$~~~~~~$|...|\n",
"| 1 | 1 | 0001 |$~~~~~~$| 17 | 11 | 10001|$~~~~~~$| 33 | 21 |100001|$~~~~~~$|...|\n",
"| 2 | 2 | 0010 |$~~~~~~$| 18 | 12 | 10010|$~~~~~~$| 34 | 22 |100010|$~~~~~~$|...|\n",
"| 3 | 3 | 0011 |$~~~~~~$| 19 | 13 | 10011|$~~~~~~$| 35 | 23 |100011|$~~~~~~$|...|\n",
"| 4 | 4 | 0100 |$~~~~~~$| 20 | 14 | 10100|$~~~~~~$| 36 | 24 |100100|$~~~~~~$|...|\n",
"| 5 | 5 | 0101 |$~~~~~~$| 21 | 15 | 10101|$~~~~~~$| 37 | 25 |100101|$~~~~~~$|...|\n",
"| 6 | 6 | 0110 |$~~~~~~$| 22 | 16 | 10110|$~~~~~~$| 38 | 26 |100110|$~~~~~~$|...|\n",
"| 7 | 7 | 0111 |$~~~~~~$| 23 | 17 | 10111|$~~~~~~$| 39 | 27 |100111|$~~~~~~$|...|\n",
"| 8 | 8 | 1000 |$~~~~~~$| 24 | 18 | 11000|$~~~~~~$| 40 | 28 |101000|$~~~~~~$|...|\n",
"| 9 | 9 | 1001 |$~~~~~~$| 25 | 19 | 11001|$~~~~~~$| 41 | 29 |101001|$~~~~~~$|...|\n",
"| 10 | a | 1010 |$~~~~~~$| 26 | 1a | 11010|$~~~~~~$| 42 | 2a |101010|$~~~~~~$|...|\n",
"| 11 | b | 1011 |$~~~~~~$| 27 | 1b | 11011|$~~~~~~$| 43 | 2b |101011|$~~~~~~$|...|\n",
"| 12 | c | 1100 |$~~~~~~$| 28 | 1c | 11100|$~~~~~~$| 44 | 2c |101100|$~~~~~~$|...|\n",
"| 13 | d | 1101 |$~~~~~~$| 29 | 1d | 11101|$~~~~~~$| 45 | 2d |101101|$~~~~~~$|...|\n",
"| 14 | e | 1110 |$~~~~~~$| 30 | 1e | 11110|$~~~~~~$| 46 | 2e |101110|$~~~~~~$|...|\n",
"| 15 | f | 1111 |$~~~~~~$| 31 | 1f | 11111|$~~~~~~$| 47 | 2f |101111|$~~~~~~$|...|"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"To show more examples of the above subscript convention, we pick three random entries from the table:\n",
"\n",
"$11_{10} = \\text{b}_{16} = 1011_2$\n",
"\n",
"$25_{10} = 19_{16} = 11001_2$\n",
"\n",
"$46_{10} = 2\\text{e}_{16} = 101110_2$\n",
"\n",
"The built-in [hex() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/functions.html#hex) function creates a `str` object starting with `\"0x\"` representing an `int` object's hexadecimal representation. The length depends on how many groups of four bits are implied by the corresponding binary representation.\n",
"\n",
"For `0` and `1`, the hexadecimal representation is similar to the binary one."
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0x0'"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hex(0)"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0x1'"
]
},
"execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hex(1)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Whereas `bin(3)` already requires two digits, one is enough for `hex(3)`."
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0x3'"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hex(3) # bin(3) => \"0b11\"; two digits needed"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"For `10` and `15`, we see the letter digits for the first time."
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0xa'"
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hex(10)"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0xf'"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hex(15)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The binary representation of `123`, `0b_111_1011`, can be viewed as *two* groups of four bits, $0111$ and $1011$, that are encoded as $7$ and $\\text{b}$ in hexadecimal (cf., table above)."
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b1111011'"
]
},
"execution_count": 38,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(123)"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0x7b'"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hex(123)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"To obtain a *new* `int` object with the value `123`, we call the [int() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/functions.html#int) built-in with a properly formatted `str` object and `base=16` as arguments."
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"123"
]
},
"execution_count": 40,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"int(\"0x7b\", base=16)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Alternatively, we could use a literal notation instead."
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"123"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"0x7b"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Hexadecimals between $00_{16}$ and $\\text{ff}_{16}$ (i.e., $0_{10}$ and $255_{10}$) are commonly used to describe colors, for example, in web development but also graphics editors. See this [online tool](https://www.w3schools.com/colors/colors_hexadecimal.asp) for some more background."
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0x0'"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hex(0)"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0xff'"
]
},
"execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hex(255)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Just like binary representations, the hexadecimals extend to the left for larger numbers like `789`."
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0x315'"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hex(789)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"For completeness sake, we mention that there is also the [oct() <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/library/functions.html#oct) built-in to obtain an integer's **octal representation**. The logic is the same as for the hexadecimal representation, and we use *eight* instead of *sixteen* digits. That is the equivalent of viewing the binary representations in groups of three bits. As of today, octal representations have become less important, and the data science practitioner may probably live without them quite well."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"## Negative Values"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"While there are conventions that model negative integers with $0$s and $1$s in memory (cf., [Two's Complement <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Two%27s_complement)), Python manages that for us, and we do not look into the theory here for brevity. We have learned all that a practitioner needs to know about how integers are modeled in a computer. The [Further Resources <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_nb.png\">](https://nbviewer.jupyter.org/github/webartifex/intro-to-python/blob/main/05_numbers/06_resources.ipynb) section at the end of this chapter provides a video tutorial on how the [Two's Complement <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Two%27s_complement) idea works.\n",
"\n",
"The binary and hexadecimal representations of negative integers are identical to their positive counterparts except that they start with a minus sign `-`. However, as the video tutorial at the end of the chapter reveals, that is *not* how the bits are organized in memory."
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'-0b11'"
]
},
"execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(-3)"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'-0x3'"
]
},
"execution_count": 46,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hex(-3)"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'-0b11111111'"
]
},
"execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(-255)"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'-0xff'"
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"hex(-255)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Bitwise Operators"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Now that we know how integers are represented with $0$s and $1$s, we look at ways of working with the individual bits, in particular with the so-called **[bitwise operators](https://wiki.python.org/moin/BitwiseOperators)**: As the name suggests, the operators perform some operation on a bit by bit basis. They only work with and always return `int` objects.\n",
"\n",
"We keep this overview rather short as such \"low-level\" operations are not needed by the data science practitioner regularly. Yet, it is worthwhile to have heard about them as they form the basis of all of arithmetic in computers.\n",
"\n",
"The first operator is the **bitwise AND** operator `&`: It looks at the bits of its two operands, `11` and `13` in the example, in a pairwise fashion and if *both* operands have a $1$ in the *same* position, the resulting integer will have a $1$ in this position as well. Otherwise, the resulting integer will have a $0$ in this position. The binary representations of `11` and `13` both have $1$s in their respective first and fourth bits, which is why `bin(11 & 13)` evaluates to `Ob_1001` or `9`."
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [
{
"data": {
"text/plain": [
"9"
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"11 & 13"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b1011 & 0b1101'"
]
},
"execution_count": 50,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(11) + \" & \" + bin(13) # to show the operands' bits"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b1001'"
]
},
"execution_count": 51,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(11 & 13)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"`0b_1001` is the binary representation of `9`."
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"9"
]
},
"execution_count": 52,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"0b_1001"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The **bitwise OR** operator `|` evaluates to an `int` object whose bits are set to $1$ if the corresponding bits of either *one* or *both* operands are $1$. So in the example `9 | 13` only the second bit is $0$ for both operands, which is why the expression evaluates to `0b_1101` or `13`."
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"13"
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"9 | 13"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b1001 | 0b1101'"
]
},
"execution_count": 54,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(9) + \" | \" + bin(13) # to show the operands' bits"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b1101'"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(9 | 13)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"`0b_1101` evaluates to an `int` object with the value `13`."
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"13"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"0b_1101"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The **bitwise XOR** operator `^` is a special case of the `|` operator in that it evaluates to an `int` object whose bits are set to $1$ if the corresponding bit of *exactly one* of the two operands is $1$. Colloquially, the \"X\" stands for \"exclusive.\" The `^` operator must *not* be confused with the exponentiation operator `**`! In the example, `9 ^ 13`, only the third bit differs between the two operands, which is why it evaluates to `0b_100` omitting the leading $0$."
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"9 ^ 13"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b1001 ^ 0b1101'"
]
},
"execution_count": 58,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(9) + \" ^ \" + bin(13) # to show the operands' bits"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b100'"
]
},
"execution_count": 59,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(9 ^ 13)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"`0b_100` evaluates to an `int` object with the value `4`."
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 60,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"0b_100"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"The **bitwise NOT** operator `~`, sometimes also called **inversion** operator, is said to \"flip\" the $0$s into $1$s and the $1$s into $0$s. However, it is based on the aforementioned [Two's Complement <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_wiki.png\">](https://en.wikipedia.org/wiki/Two%27s_complement) convention and `~x = -(x + 1)` by definition (cf., the [reference <img height=\"12\" style=\"display: inline-block\" src=\"../static/link/to_py.png\">](https://docs.python.org/3/reference/expressions.html#unary-arithmetic-and-bitwise-operations)). The full logic behind this, while actually quite simple, is considered out of scope in this book.\n",
"\n",
"We can at least verify the definition by comparing the binary representations of `7` and `-8`: They are indeed the same."
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"text/plain": [
"-8"
]
},
"execution_count": 61,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"~7"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 62,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"~7 == -(7 + 1) # = Two's Complement"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'-0b1000'"
]
},
"execution_count": 63,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(~7)"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'-0b1000'"
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(-(7 + 1))"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"`~x = -(x + 1)` can be reformulated as `~x + x = -1`, which is slightly easier to check."
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"-1"
]
},
"execution_count": 65,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"~7 + 7"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"Lastly, the **bitwise left and right shift** operators, `<<` and `>>`, shift all the bits either to the left or to the right. This corresponds to multiplying or dividing an integer by powers of `2`.\n",
"\n",
"When shifting left, $0$s are filled in."
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"28"
]
},
"execution_count": 66,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"7 << 2"
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b111'"
]
},
"execution_count": 67,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(7)"
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b11100'"
]
},
"execution_count": 68,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(7 << 2)"
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"28"
]
},
"execution_count": 69,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"0b_1_1100"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"source": [
"When shifting right, some bits are always lost."
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"7 >> 1"
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b111'"
]
},
"execution_count": 71,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(7)"
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"'0b11'"
]
},
"execution_count": 72,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"bin(7 >> 1)"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 73,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"0b_11"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.2"
},
"livereveal": {
"auto_select": "code",
"auto_select_fragment": true,
"scroll": true,
"theme": "serif"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": false,
"sideBar": true,
"skip_h1_title": true,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {
"height": "calc(100% - 180px)",
"left": "10px",
"top": "150px",
"width": "384px"
},
"toc_section_display": false,
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Reference in a new issue View git blame Copy permalink