1-bit and 2-bit Characters in Python

What Are 1-bit and 2-bit Characters?

In computers, everything is stored in the form of bits, i.e., the smallest pieces of data that can be either 0 or 1. Now, when we talk about 1-bit or 2-bit characters, we mean how many of these bits are used to make a single character (like a letter or symbol).

• A 1-bit character is just a single 0. It counts as one character by itself.
• A 2-bit character is made of two bits and can be either 10 or 11.

If we are given a list of bits (containing only 0s and 1s) that ends with 0. The list represents a sequence of characters encoded in either 1-bit or 2-bit format.

The task is to figure out if the last 0 in the array is a standalone 1-bit character or if it is part of a 2-bit character in Python.

Let's explore a few scenarios to understand this problem in a better way:

Scenario 1

Input: bits = [1, 0, 0] Output: True Explanation: The bits represent 10 (2-bit) and 0 (1-bit). So the last character is a 1-bit character. 

Scenario 2

Input: bits = [1, 1, 1, 0] Output: False Explanation: The bits are read as 11 and 10. So the last character is part of a 2-bit character, not a standalone 0. 

Algorithm to find 1-bit and 2-bit Characters in Python

To determine whether the last character is a 1-bit character in Python, follow these steps:

• Initialize a pointer i = 0. This will help us move through the list of bits.
• Loop through the list until you reach the second-last bit (i.e., while i < len(bits) - 1):
• If bits[i] == 0, it's a 1-bit character. So, move "i" ahead by 1 step.
• If bits[i] == 1, it's a 2-bit character (either 10 or 11). So, move "i" ahead by 2 steps.
• When the loop finishes, you will be at index i. Now, check:
• If "i" is exactly equal to the last index (len(bits) - 1), then the last character is a 1-bit character. So, return True.
• If "i" has gone past the last index, then the last 0 was part of a 2-bit character. So, return False.

Python Implementation

The following is an example to check whether the last character in the bit sequence is a 1-bit character or not in Python:

def isOneBitCharacter(bits): # Start from the first bit i = 0 # Loop through the bits until just before the last one while i < len(bits) - 1: # If we find a 1, it's a 2-bit character (either 10 or 11) # So we skip the next bit as well if bits[i] == 1: i += 2 # If we find a 0, it's a 1-bit character # So move one step ahead else: i += 1 # After the loop, check if we are exactly at the last bit # If yes, it means the last character is a 1-bit character return i == len(bits) - 1 # Example usage bits1 = [1, 0, 0] bits2 = [1, 1, 1, 0] # Calling the function and printing the results print("Output for bits1:", isOneBitCharacter(bits1)) print("Output for bits2:", isOneBitCharacter(bits2)) 

We get the output as shown below:

Output for bits1: True Output for bits2: False 

Conclusion

In this article, we learned how to determine if the last 0 in a bit sequence is a standalone 1-bit character or part of a 2-bit character. If we land exactly on the last bit, it's a 1-bit character; otherwise, it's part of a 2-bit character.