In this article, you will learn how to implement the bit array. As the name suggests, a bit array is an array consisting of bit values, i.e., 0s and 1s.
How to implementation a Bit Array?
One straightforward approach that comes to our mind while implementing a bit array is to create an array of
n size where each bit value, 0 or 1, is stored at an index.
For example, array=1, array=1, array=0, and array=0 stores 0011, where bit at index 0 is the least significant value and bit at index 3 is the most significant.
Simple, right? The problem with this approach is that we are wasting a lot of memory space. We are storing 0s and 1s (which are integers), and each integer typically takes 4 bytes (32 bits) in the memory. Therefore, we are using 16 bytes (128 bits) to store 4 bits only, and it is very inefficient.
A better approach would be to utilize each bit of an array item. This concept is illustrated in the figure below.
A bit array generally includes three operations, i.e., set a bit at a specific position, reset a bit, and get the bit value at a particular location.
Set a Bit
Let’s say we want to create a bit array of size 64 bits. For that, we will need an array of length 2, as each array item can store 32 bits. Bits from 0-31 will be stored at index 0 and bits from 32-63 at index 1. Initially, all the bits will have a 0 value. To set a particular bit, for example, a bit at the position
k in a bit array, we need to find two things:
- The index of an array. To find it, we need to divide the bit position
- The offset value at that index, which is the remainder when
kis divided by 32.
For example, let’s say we want to set the bit 35. The array index will be 35/32 = 1 (integer division) and the offset will be 35%32 = 3.
After that, we define a temporary variable of 32 bits containing 1 at the least significant place. We shift it to the offset position. Then, we perform the bitwise or operation between the temporary variable and the
array[index] so that all the values at
array[index] remain unchanged, except the bit at the offset position, which gets changed to 1.
Let’s see its implementation.
bitarray = [0, 0] def setBit(bitarray, k): index = k//32 #find the index of the array bit_pos = k%32 #find the offset temp = 0b00000000000000000000000000000001 temp = temp << bit_pos #shift left bitarray[index] |= temp #set the bit return bitarray k=35 bitarray = setBit(bitarray, k) print(bin(bitarray)) #print the bits at the index 1of the bit array.
Reset a Bit
Similar to setting a bit, we need to find the index and the offset at that index. Then, we need to set the bit of the temporary variable at the offset position. Since we need to make that 0, we apply the bitwise not operation such that all the other values get converted to 1, and the bit value at the offset position gets changed to 0. After that, we apply the bitwise and operation between the temporary variable and
array[index] to reset the bit.
Consider the following code.
def resetBit(bitarray, k): index = k//32 #find the index of the array bit_pos = k%32 #find the offset temp = 0b00000000000000000000000000000001 temp = temp << bit_pos #shift left temp = ~temp # bitwise not bitarray[index] &= temp #reset the bit return bitarray bitarray = resetBit(bitarray, k) print(bin(bitarray)) #print the bits at the index 1
In the above example, we clear the bit at position 35 that was previously set.
Get a Bit
To get a bit at a specific position, we shift 1 to the offset position in the temporary variable. Then, we perform the bitwise and operation between the
array[index] and the temporary variable. If the output is 1, then the
kth bit is also 1. Otherwise, it is 0.
Consider the following code.
def getBit(bitarray, k): index = k//32 #find the index of the array bit_pos = k%32 #find the offset temp = 0b00000000000000000000000000000001 temp = temp << bit_pos #shift left if (bitarray[index] & temp): return 1 else: return 0 k=35 bitarray = setBit(bitarray, k) print(getBit(bitarray, 35)) print(getBit(bitarray, 0))