What Is a Bit Vector?

This is what a bit vector is.

A bit vector is like an array of bits.

So if you want to know what a bit vector is in detail and how to create and use one, then you’re in the right place.

Let’s jump right in!

Understand Bit Vectors

You’ll learn what bit vectors are, how they look, and what values their elements can take. 

Moreover, how to create them, display them, and do other operations with bit vectors based on integers and bitwise operations. 

Furthermore, the Python bitarray library allows you to work with bit vectors more efficiently. 

Lastly, the advantages and applications of bit vectors.

You probably know that computers store data in zeros and ones. 

For calculations, computers use a binary number system. In this system, there are only two digits: 0 and 1. 

Therefore, to encode any number greater than 1, you must use more digits. You have to encode a number with a series of 0s and 1s. 

One such bit is called a bit. It’s one digit that says 1 or 0, yes or no, true or false.

A structure consisting of multiple bits is called a bit vector or bit array.

Usually, programming languages don’t address a specific bit. This limitation is due to the way processors and memory registers work. 

Nevertheless, there are some ways to manipulate individual bits in a bit vector.

Here’s how:

Basic Bit Vector Operations

Let’s look at basic operations with bit vectors.

Setting a specific bit to 1

Suppose you have a bit vector:

bv = 1101011000010110

You want the value of place 4 to be 1 (right to left). If it were just a simple array, you could write something like this:

bv[4] = 1

As mentioned above, most languages wouldn’t let you do that. But you can always use bitwise OR.

Bitwise OR is actually standard functionally in the vast majority of programming languages, including Python.

1101011000010110
OR
0000000000001000
------
1101011000011110

OR operations return the bits from the original bit vector for every 0 in the bitmask. Unless the bitmask says 1 for a bit. Then this bit is returned as 1.

Setting a Specific Bit to 0

In the same way, you can set a specific bit to 0 using a mask. You need to use the bitwise AND operator. In the mask, you set every bit to 1 but the target bit:

1101011000011110
AND
1111111111110111
------
1101011000010110

Checking if a Specific Bit Is 1

You can do this with a bitwise AND and then compare the result to zero:

1101011000010110
AND
0000000000001000
------
0000000000000000 == 0 -> bit not set to one

1101011000010110
AND
0000000000000100
------
0000000000000100! = 0 -> bit set to one

Inverting the State of a Certain Bit

You can also invert a specific bit. That is, toggle it to 0 if it was 1 or to 1 if it was 0. To do this, use a bitwise XOR:

110 101 100 0010110
XOR
000 000 000 0001000
------
110 101 100 0011110

Inverting the Whole Vector

You can also invert entire bit vectors. For this, use the bitwise NOT operation:

NOT
1101011000010110
------
0010100111101001

A Simple Implementation of Operations With Bit Vectors in Python

Let’s see how to do this in Python. 

For bit vectors of small lengths (up to 128 bits), you can use integers for education purposes, for example. It’s easy to show a number in binary with f-strings:

>> bv = int("1101011000010110", 2)  
>> print(bv) 
 54806
>> print(f"{bv: 016b}") 
 1101011000010110

In the first line, the int constructor is used with parameter 2 to convert the string to an integer. 

If you print out this bit vector, you get 54806. You can print any number in binary using f-string. 

You set:

• The format for outputting the number: b (binary)
• The length of the string: 16
• How to fill the empty space: 0 

You can learn more about f-strings here.

To form a mask, you can use the bit shift operation:

• Left shift: <<
• Right shift: >>

Let’s use our example and set the bits vectors’ fourth bit to 1. To do this, take 1 and move it 3 places left. 

Then, apply the bitwise logical OR (|) operation:

m = 1 << 3  
res = bv | m  
  
print(f"{bv: 016b}")  
print("OR")  
print(f"{m: 016b}")  
print("-----------")  
print(f"{res : 016b}")

1101011000010110  
OR  
0000000000001000  
-----------  
1101011000011110  

If you’d like to set the bit on place 4 and the bit on place 12 to 1 in parallel, you’d use bit shift and logical OR:

m = 1 << 3 | 1 << 11  
res = bv | m  
  
print(f"{bv: 016b}")  
print("OR")  
print(f"{m: 016b}")  
print("-----------")  
print(f"{res : 016b}")

1101011000010110  
OR  
0000100000001000  
-----------  
1101111000011110  

As you can see, bit vectors provide parallel execution. You set two bits to 1 in the same way as one bit. Only the mask is different.

Let’s try another example. Let’s set the third bit of bv to zero. 

First, make a 16 bit mask. For this shift 1 by sixteen places to get 1 and sixteen 0: 10000000000000000. 

Then subtract one from that number. You’re getting sixteen binary units: 1111111111111111.

In order to understand how that works, let’s take a look at a smaller mask:

Let’s take 1 and move it 4 digits to the left: 10000. As decimal, that’s 16. 

Subtract one and you get 15 in decimal. And 1111 in binary: 8 + 4 + 2 + 1.

Next, take a bitwise XOR (^) and set the mask’s third bit to zero. After forming the mask, apply the bitwise AND (&) operation:

m = ((1 << 16) - 1) ^ (1 << 2)  
res = bv & m  
  
print(f"{bv: 016b}")  
print("AND")  
print(f"{m: 016b}")  
print("-----------")  
print(f"{res : 016b}")  

1101011000010110  
AND  
1111111111111011  
-----------  
1101011000010010 

Along with assignment operators such as * =, + =, the operators | =, ^ =, & = also work in Python. 

These operators evaluate the appropriate operation on the original value and then assign a new value to the variable.

Let’s look at some examples:

>> bv = int ("1101011000010110", 2)  
1101011000010110  

Set 14th bit to 1:

>> bv | = 1 << 13  
1111011000010110  

Set 14th bit to 0: 

>> bv & = ~ (1 << 13)  
1101011000010110

Toggle 16th bit:  

>> bv ^ = 1 << 15  
0101011000010110

Library for Dealing With Bit Vectors (Python)

Of course, using the int type for bit arrays is not correct; Python uses the bytearray type for that.

To get the full advantage of bitmaps, you can use the existing libraries with implemented basic and advanced operations. For example, the library bitarray. You can install it with the following command in the terminal:

! pip install bitarray

The library is entirely implemented in C, so you can work with bitmaps quickly. At the same time, you can use bit arrays like regular sequences in Python:

• Access by indices
• Make slices
• Add items
• Delete items

Here’s an example of using this library to set a bit:

from bitarray import bitarray  
bv = bitarray ("1101011000010110")  
print(bv)  
bv[1] = 0  
print(bv)

bitarray ('1101011000010110')  
bitarray ('1001011000010110') 

See, you can do this in an elementary and very intuitive way. Notice how the bits are numbered left to right and starting at zero, as with all Python sequences.

Additionally, this library allows you to use huge bit arrays, up to two gigabytes on a 32-bit operating system. 

This library supports:

• All bitwise binary operations for vectors
• Sequential search
• Conversion to other binary data formats
• And others

Bit Vector Benefits and Uses

What are the benefits of bit vectors, and where do you use them?

First of all, they’re really compact. 

You can store 8 independent values in one byte. 

Since a computer can address a bit array directly in memory, you can do anything inside the bit array without using memory access. 

Bitmaps provide parallel computations. You can change all the bits in a vector or just one in the same amount of time.

Their advantages dictate the application of bit vectors. For example, they’re useful for storing groups of boolean flags or ordered sequences of boolean values. 

You can also use bit vectors in prioritization implementations like the Linux operating system. It often uses bit arrays to allocate various memory structures such as: 

• Inodes
• Disk sectors
• Memory pages

Also, bitmaps and operations with them are necessary to build compact and concise data structures, for which it is critical to use the least amount of memory.