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

Solution Notebook

Problem: Implement common bit manipulation operations: get_bit, set_bit, clear_bit, clear_bits_msb_to_index, clear_bits_msb_to_lsb, update_bit.

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):
        mask = 1 << index
        return self.number & mask != 0

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

    @validate_index
    def clear_bit(self, index):
        mask = ~(1 << index)
        self.number &= mask
        return self.number

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

    @validate_index
    def clear_bits_index_to_lsb(self, index):
        mask = ~((1 << index + 1) - 1)
        self.number &= mask
        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