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

# Solution Notebook¶

## Constraints¶

• Can we assume the inputs are valid?
• No
• Can we assume this fits memory?
• Yes

## Test Cases¶

• None as a number input -> Exception
• Negative index -> Exception

### get_bit¶

number   = 0b10001110, index = 3
expected = True


### set_bit¶

number   = 0b10001110, index = 4
expected = 0b10011110


### clear_bit¶

number   = 0b10001110, index = 3
expected = 0b10000110


### clear_bits_msb_to_index¶

number   = 0b10001110, index = 3
expected = 0b00000110


### clear_bits_index_to_lsb¶

number   = 0b10001110, index = 3
expected = 0b10000000


### update_bit¶

number   = 0b10001110, index = 3, value = 1
expected = 0b10001110
number   = 0b10001110, index = 3, value = 0
expected = 0b10000110
number   = 0b10001110, index = 0, value = 1
expected = 0b10001111

## Algorithm¶

### get_bit¶

indices  7 6 5 4  3 2 1 0  index = 3
--------------------------------------------------
input    1 0 0 0  1 1 1 0  0b10001110
mask     0 0 0 0  1 0 0 0  1 << index
--------------------------------------------------
result   0 0 0 0  1 0 0 0  number & mask != 0


Complexity:

• Time: O(n)
• Space: O(n)

### set_bit¶

indices  7 6 5 4  3 2 1 0  index = 4
--------------------------------------------------
input    1 0 0 0  1 1 1 0  0b10001110
mask     0 0 0 1  0 0 0 0  1 << index
--------------------------------------------------
result   1 0 0 1  1 1 1 0  number | mask


Complexity:

• Time: O(n)
• Space: O(n)

### clear_bit¶

indices  7 6 5 4  3 2 1 0  index = 3
--------------------------------------------------
input    1 0 0 0  1 1 1 0  0b10001110
mask     0 0 0 0  1 0 0 0  1 << index
mask     1 1 1 1  0 1 1 1  ~(1 << index)
--------------------------------------------------
result   1 0 0 0  0 1 1 0  number & mask


Complexity:

• Time: O(n)
• Space: O(n)

### clear_bits_msb_to_index¶

indices  7 6 5 4  3 2 1 0  index = 3
--------------------------------------------------
input    1 0 0 0  1 1 1 0  0b10001110
mask     0 0 0 0  1 0 0 0  1 << index
mask     0 0 0 0  0 1 1 1  (1 << index) - 1
--------------------------------------------------
result   0 0 0 0  0 1 1 1  number & mask


Complexity:

• Time: O(n)
• Space: O(n)

### clear_bits_index_to_lsb¶

indices  7 6 5 4  3 2 1 0  index = 3
--------------------------------------------------
input    1 0 0 0  1 1 1 0  0b10001110
mask     0 0 0 1  0 0 0 0  1 << index + 1
mask     0 0 0 0  1 1 1 1  (1 << index + 1) - 1
mask     1 1 1 1  0 0 0 0  ~((1 << index + 1) - 1)
--------------------------------------------------
result   1 0 0 0  0 0 0 0  number & mask


Complexity:

• Time: O(n)
• Space: O(n)

### update_bit¶

• Use get_bit to see if the value is already set or cleared
• If not, use set_bit if setting the value or clear_bit if clearing the value

Complexity:

• Time: O(n)
• Space: O(n)

## Code¶

In [1]:
def validate_index(func):
def validate_index_wrapper(self, *args, **kwargs):
for arg in args:
if arg < 0:
raise IndexError('Invalid index')
return func(self, *args, **kwargs)
return validate_index_wrapper

In [2]:
class Bit(object):

def __init__(self, number):
if number is None:
raise TypeError('number cannot be None')
self.number = number

@validate_index
def get_bit(self, index):
return self.number & mask != 0

@validate_index
def set_bit(self, index):
return self.number

@validate_index
def clear_bit(self, index):
return self.number

@validate_index
def clear_bits_msb_to_index(self, index):
mask = (1 << index) - 1
return self.number

@validate_index
def clear_bits_index_to_lsb(self, index):
mask = ~((1 << index + 1) - 1)
return self.number

@validate_index
def update_bit(self, index, value):
if value is None or value not in (0, 1):
raise Exception('Invalid value')
if self.get_bit(index) == value:
return self.number
if value:
self.set_bit(index)
else:
self.clear_bit(index)
return self.number


## Unit Test¶

In [3]:
%%writefile test_bit.py
import unittest

class TestBit(unittest.TestCase):

def test_bit(self):
number = int('10001110', base=2)
bit = Bit(number)
self.assertEqual(bit.get_bit(index=3), True)
expected = int('10011110', base=2)
self.assertEqual(bit.set_bit(index=4), expected)
bit = Bit(number)
expected = int('10000110', base=2)
self.assertEqual(bit.clear_bit(index=3), expected)
bit = Bit(number)
expected = int('00000110', base=2)
self.assertEqual(bit.clear_bits_msb_to_index(index=3), expected)
bit = Bit(number)
expected = int('10000000', base=2)
self.assertEqual(bit.clear_bits_index_to_lsb(index=3), expected)
bit = Bit(number)
self.assertEqual(bit.update_bit(index=3, value=1), number)
bit = Bit(number)
expected = int('10000110', base=2)
self.assertEqual(bit.update_bit(index=3, value=0), expected)
bit = Bit(number)
expected = int('10001111', base=2)
self.assertEqual(bit.update_bit(index=0, value=1), expected)
print('Success: test_bit')

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

if __name__ == '__main__':
main()

Overwriting test_bit.py

In [4]:
%run -i test_bit.py

Success: test_bit