This notebook was prepared by Donne Martin. Source and license info is on GitHub.
We should make a note that Python does not have a logical right shift operator built in. We can either use a positive number or implement one for a 32 bit number:
num % 0x100000000 >> n
Complexity:
class Bits(object):
MAX_BITS = 32
def _build_seen_list(self, num):
seen = []
looking_for = 0
count = 0
for _ in range(self.MAX_BITS):
if num & 1 != looking_for:
seen.append(count)
looking_for = not looking_for
count = 0
count += 1
num >>= 1
seen.append(count)
return seen
def flip_bit(self, num):
if num is None:
raise TypeError('num cannot be None')
if num == -1:
return self.MAX_BITS
if num == 0:
return 1
seen = self._build_seen_list(num)
max_result = 0
looking_for = 0
for index, count in enumerate(seen):
result = 0
# Only look for zeroes
if looking_for == 1:
looking_for = not looking_for
continue
# First iteration, take trailing zeroes
# or trailing ones into account
if index == 0:
if count != 0:
# Trailing zeroes
try:
result = seen[index + 1] + 1
except IndexError:
result = 1
# Last iteration
elif index == len(seen) - 1:
result = 1 + seen[index - 1]
else:
# One zero
if count == 1:
result = seen[index + 1] + seen[index - 1] + 1
# Multiple zeroes
else:
result = max(seen[index + 1], seen[index - 1]) + 1
if result > max_result:
max_result = result
looking_for = not looking_for
return max_result
%%writefile test_flip_bit.py
import unittest
class TestBits(unittest.TestCase):
def test_flip_bit(self):
bits = Bits()
self.assertRaises(TypeError, bits.flip_bit, None)
self.assertEqual(bits.flip_bit(0), 1)
self.assertEqual(bits.flip_bit(-1), bits.MAX_BITS)
num = int('00001111110111011110001111110000', base=2)
expected = 10
self.assertEqual(bits.flip_bit(num), expected)
num = int('00000100111011101111100011111011', base=2)
expected = 9
self.assertEqual(bits.flip_bit(num), expected)
num = int('00010011101110111110001111101111', base=2)
expected = 10
self.assertEqual(bits.flip_bit(num), expected)
print('Success: test_print_binary')
def main():
test = TestBits()
test.test_flip_bit()
if __name__ == '__main__':
main()
Overwriting test_flip_bit.py
%run -i test_flip_bit.py
Success: test_print_binary