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?

Naïve Approach

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[0]=1, array[1]=1, array[2]=0, and array[3]=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.

Another Approach

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:

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[1])) #print the bits at the index 1of the bit array.

Output

0b1000

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[1])) #print the bits at the index 1

Output

0b0

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))

Output

1

0