This notebook was prepared by Donne Martin. Source and license info is on GitHub.

# Solution Notebook¶

## Constraints¶

• Can we assume j > i?
• Yes
• Can we assume i through j have enough space for m?
• Yes
• Can we assume the inputs are valid?
• No
• Can we assume this fits memory?
• Yes

## Test Cases¶

• None as an input -> Exception
• Negative index for i or j -> Exception
• General case
i = 2, j = 6
j    i
n      = 0000 0100 0011 1101
m      = 0000 0000 0001 0011
result = 0000 0100 0100 1101


## Algorithm¶

                    j    i
n      = 0000 0100 0011 1101
m      = 0000 0000 0001 0011

lmask  = 1111 1111 1111 1111  -1
lmask  = 1111 1111 1000 0000  -1 << (j + 1)

rmask  = 0000 0000 0000 0001   1
rmask  = 0000 0000 0000 0100   1 << i
rmask  = 0000 0000 0000 0011   (1 << i) -1

n      = 0000 0100 0011 1101
mask   = 1111 1111 1000 0011   n & mask
--------------------------------------------------
n2     = 0000 0100 0000 0001

n2     = 0000 0100 0000 0001
mask2  = 0000 0000 0100 1100   m << i
--------------------------------------------------
result = 0000 0100 0100 1101   n2 | mask2


Complexity:

• Time: O(b), where b is the number of bits
• Space: O(b), where b is the number of bits

## Code¶

In [1]:
class Bits(object):

def insert_m_into_n(self, m, n, i, j):
if None in (m, n, i, j):
raise TypeError('Argument cannot be None')
if i < 0 or j < 0:
raise ValueError('Index cannot be negative')
left_mask = -1 << (j + 1)
right_mask = (1 << i) - 1
# Clear bits from j to i, inclusive
n_cleared = n & n_mask
# Shift m into place before inserting it into n
m_mask = m << i
return n_cleared | m_mask


## Unit Test¶

In [2]:
%%writefile test_insert_m_into_n.py
import unittest

class TestBit(unittest.TestCase):

def test_insert_m_into_n(self):
n = int('0000010000111101', base=2)
m = int('0000000000010011', base=2)
expected = int('0000010001001101', base=2)
bits = Bits()
self.assertEqual(bits.insert_m_into_n(m, n, i=2, j=6), expected)
print('Success: test_insert_m_into_n')

def main():
test = TestBit()
test.test_insert_m_into_n()

if __name__ == '__main__':
main()

Overwriting test_insert_m_into_n.py

In [3]:
%run -i test_insert_m_into_n.py

Success: test_insert_m_into_n