fun_with_bitstrings.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Joe's byte-packing cellular automata thing\n",
    "\n",
    "Gonna start by re-stating the problem, which I am probably confused about, so that any further confusion below which follows directly from my *initial* confusion will be more obvious.\n",
    "\n",
    "Here's what we want to do:\n",
    "\n",
    "    Given an input string containing a bitmask:\n",
    "    For each bit in the input string:\n",
    "      output a full byte containing all bits either set or unset depending on the initial bit.\n",
    "      \n",
    "Starting with an input string of 8 bits, we'd output something 64 bits long. We can then feed this 64-bit string back in as input to get a 128-bit output. We could call this multiple times on the output of the previous iteration to create very long strings.\n",
    "\n",
    "I'm going to do this in Python because I haven't played with Python for far too long, and I've been wanting to play with Jupyter notebook for a while…"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "bitstring = \"00101011\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Doing it with strings\n",
    "\n",
    "This is probably the simplest way. The downside is that it uses more memory (not a problem unless we get to very large numbers, but a few iterations could do that easily) and it's probably slower (not a problem unless we're doing it often)\n",
    "\n",
    "We look at each character of the input string in turn and build a corresponding output string:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input:   00101011\n",
      "Output:  0000000000000000111111110000000011111111000000001111111111111111\n"
     ]
    }
   ],
   "source": [
    "output = \"\"\n",
    "for bit in bitstring:\n",
    "    output += bit * 8\n",
    "    \n",
    "print(\"Input:  \", bitstring)\n",
    "print(\"Output: \", output)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can do it again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input:   0000000000000000111111110000000011111111000000001111111111111111\n",
      "Output:  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\n"
     ]
    }
   ],
   "source": [
    "bitstring = output\n",
    "output = \"\"\n",
    "for bit in bitstring:\n",
    "    output += bit * 8\n",
    "    \n",
    "print(\"Input:  \", bitstring)\n",
    "print(\"Output: \", output)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can create a function to repeat this process for a given number of iterations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input:         00101011\n",
      "1 Iteration:   0000000000000000111111110000000011111111000000001111111111111111\n",
      "2 Iterations:  00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\n",
      "3 Iterations:  0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\n"
     ]
    }
   ],
   "source": [
    "def expand_iteratively (bitstring, iterations):    \n",
    "    while iterations > 0:\n",
    "        output = \"\"\n",
    "        \n",
    "        for bit in bitstring:\n",
    "            output += bit * 8\n",
    "        \n",
    "        bitstring = output\n",
    "        iterations -= 1\n",
    "    \n",
    "    return output\n",
    "\n",
    "bitstring = \"00101011\"    \n",
    "print(\"Input:        \", bitstring)\n",
    "print(\"1 Iteration:  \", expand_iteratively(bitstring, 1))\n",
    "print(\"2 Iterations: \", expand_iteratively(bitstring, 2))\n",
    "print(\"3 Iterations: \", expand_iteratively(bitstring, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or we could do this recursively:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input:     00101011\n",
      "Depth 1:   0000000000000000111111110000000011111111000000001111111111111111\n",
      "Depth 2:   00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\n",
      "Depth 3:   0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111\n"
     ]
    }
   ],
   "source": [
    "def expand_recursively (bitstring, depth):\n",
    "    if depth > 0:\n",
    "        return expand_recursively(''.join([bit*8 for bit in bitstring]), depth - 1)\n",
    "    else:\n",
    "        return bitstring\n",
    "\n",
    "bitstring = \"00101011\"    \n",
    "print(\"Input:    \", bitstring)\n",
    "print(\"Depth 1:  \", expand_recursively(bitstring, 1))\n",
    "print(\"Depth 2:  \", expand_recursively(bitstring, 2))\n",
    "print(\"Depth 3:  \", expand_recursively(bitstring, 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### side note:\n",
    "\n",
    "This:\n",
    "\n",
    "    output = ''.join([bit*8 for bit in bitstring])\n",
    "    \n",
    "Is just a shorter, more \"pythonic\" way of saying this:\n",
    "\n",
    "    output = \"\"\n",
    "    for bit in bitstring:\n",
    "      output += bit * 8\n",
    "\n",
    "…except that the first version creates a list and then joins the elements into a string with an empty string as delimiter, while the second version just builds the string up via concatenation as we go."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## FIXME:\n",
    "\n",
    "I want to show how to do this with integers and bitwise operators too, partly for the sake of education and partly out of curiosity about resource usage (memory and CPU time) on larger numbers of iterations.\n",
    "\n",
    "The next bit is mostly me thinking out loud…"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "initial input:     00111011\n",
      "Converted to int:  59\n",
      "Converted back:    00111011\n"
     ]
    }
   ],
   "source": [
    "bitstring = \"00111011\"\n",
    "byte = int(bitstring, 2)\n",
    "print(\"initial input:    \", bitstring)\n",
    "print(\"Converted to int: \", byte)\n",
    "print(\"Converted back:   \", \"{0:08b}\".format(byte))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "byte is  43\n",
      "…right-most bit is set!\n",
      "byte is  21\n",
      "…right-most bit is set!\n",
      "byte is  10\n",
      "byte is  5\n",
      "…right-most bit is set!\n",
      "byte is  2\n",
      "byte is  1\n",
      "…right-most bit is set!\n",
      "input string:  00101011\n",
      "output string: 00101011\n"
     ]
    }
   ],
   "source": [
    "bitstring = \"00101011\"\n",
    "byte = int(bitstring, 2)\n",
    "output = \"\"\n",
    "\n",
    "while byte > 0:\n",
    "    print(\"byte is \", byte)\n",
    "    if byte & 1:\n",
    "        # right-most bit is set\n",
    "        print(\"…right-most bit is set!\")\n",
    "        output = \"1\" + output\n",
    "    else:\n",
    "        output = \"0\" + output\n",
    "    byte = byte >> 1\n",
    "    \n",
    "print(\"input string: \", bitstring)\n",
    "print(\"output string:\", '{:0>8}'.format(output)) # we stop generating output once only zeros remain, so have to pad it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}