{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "This notebook was prepared by [Donne Martin](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solution Notebook" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem: Given two 16 bit numbers, n and m, and two indices i, j, insert m into n such that m starts at bit j and ends at bit i.\n", "\n", "* [Constraints](#Constraints)\n", "* [Test Cases](#Test-Cases)\n", "* [Algorithm](#Algorithm)\n", "* [Code](#Code)\n", "* [Unit Test](#Unit-Test)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Constraints\n", "\n", "* Can we assume j > i?\n", " * Yes\n", "* Can we assume i through j have enough space for m?\n", " * Yes\n", "* Can we assume the inputs are valid?\n", " * No\n", "* Can we assume this fits memory?\n", " * Yes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Test Cases\n", "\n", "* None as an input -> Exception\n", "* Negative index for i or j -> Exception\n", "* General case\n", "\n", "
```\n",
"i = 2, j = 6\n",
"                    j    i\n",
"n      = 0000 0100 0011 1101\n",
"m      = 0000 0000 0001 0011\n",
"result = 0000 0100 0100 1101\n",
"```
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithm\n", "\n", "
```\n",
"                    j    i\n",
"n      = 0000 0100 0011 1101\n",
"m      = 0000 0000 0001 0011\n",
"\n",
"lmask  = 1111 1111 1111 1111  -1\n",
"lmask  = 1111 1111 1000 0000  -1 << (j + 1)\n",
"\n",
"rmask  = 0000 0000 0000 0001   1\n",
"rmask  = 0000 0000 0000 0100   1 << i\n",
"rmask  = 0000 0000 0000 0011   (1 << i) -1\n",
"\n",