The basics of bit manipulation

Introduction to bits#

Computers do not understand natural languages as humans do. Instead, a computer is encoded at the lowest level to a series of ones and zeroes, called binary code. This code is read by the computer as instructions, telling it what to do next.

A single digit of a binary sequence is called a bit (or, binary digit), and can be either a one or a zero. Bits are the smallest unit of data used by computers to write instructions.

The binary number system runs on bits, which are base-2 numbers representing a logical state of either 0 or 1. Instructions at the processor level are written in machine language using bits. Any program written in any programming language, such as Java or Python, must be converted into machine language before execution.

A binary sequence (a sequence of bits) is read from right to left. In this case, we call the rightmost bit, the Least Significant Bit (LSB), and the leftmost bit, the Most Significant Bit (MSB).

A binary sequence of 8 bits (byte) can store any number from 0 to 255. However, historically, a byte represents different lengths of binary sequences in different computer architectures. For example, early IBM PCs used a byte to store 8 bits, while later models used a byte to store 6 or 7 bits. Similarly, a binary sequence consisting of multiple bytes (sometimes referred to as a “word”) can represent different lengths as well.

Converting a binary sequence to decimal#

Now, let’s learn how to convert a binary sequence (base-2) to a decimal number (base-10). First, we need to number our binary sequence so that the left-most bit is numbered as the $0^{th}$ bit and the right-most bit as the $n^{th}$ bit.

To convert the binary sequence into a decimal number, we multiply each $i^{th}$ bit by $2^i$, and then sum the resulting products.

Here’s an example.

Problem Statement: Convert binary sequence $(1011)_2$ to a decimal number

Solution:

$$(1\times 2^3)+(0\times 2^2)+(1\times 2^1)+(1\times 2^0)=8+2+1=(11)_{10}$$

Basics of bit manipulation: Operators#

Bit manipulation is the process of manipulating bits or groups of bits in a byte. Bit manipulation is often used to perform operations on data that are otherwise difficult or impossible to perform with traditional operator precedence.

You can perform the following bitwise operations on individual bits:

AND operator (&)#

The AND operator (&) takes in two binary values and produces a third value whose bits are set to 1 if both of the bits compared are equal to 1. Otherwise, it returns a 0.

You can see how the logic of the AND operator works in a truth table:

We can use the AND (&) operator on two binary sequences of an equal length. To that end, you can compare each pair of bits at the same corresponding position and accumulate their result.

For example, take two binary sequences $X$ and $Y$, where

• $X=10=(1010)_2$
• $Y=9=(1001)_2$.

Let’s find $X\&Y$.

To solve this, start comparing bit pairs from right to left.

The result of the

• Rightmost pair is $0\&1=0$
• Second pair from the right is $1\& 0=0$
• Third pair is $0\&0=0$
• Leftmost pair is $1\& 1=1$

Hence, our result will be $(1000)_2=8$.

OR operator (|)#

The | operator compares two bits and returns 1 if at least one of the bits compared is equal to 1. Otherwise, it produces a 0.

In other words, the OR operator returns a 0 if and only if both of the bits compared are equal to 0.

Here’s the logic of the OR operator (|) in a truth table.

We can use the OR operator on two binary sequences of an equal length. To that end, you compare each pair of bits at the same corresponding position and accumulate their result.

For example: take two binary sequences $X$ and $Y$, where

• $X = 10 = (1010)_2$
• $Y = 9 = (1001)_2$

Let’s find $X | Y$.

Solution: $X | Y = (1010)_2$ | $(1001)_2 = (1011)_2 = (11)_{10}$

XOR operator (^)#

The XOR operator (^) stands for Exclusive OR. The XOR operator compares two bits and returns 1 if those bits are different. If both bits are the same, then XOR returns a 0.

Here’s the logic of the XOR operator (^) in a truth table.

Let’s try an example:

$$X \text{ XOR } Y = (1010)_2 \text{ XOR } (1001)_2 = (0011)_2 = 3$$

NOT operator (~)#

The operations described above are two bits operators and take two bits as input while producing a single bit as output. In contrast, the NOT operator is a single-bit operator as it takes a single bit as its input. The ~ operator flips the input bit. That is, it converts (flips) an input bit of 1 to 0 and 0 to 1.

We can apply the NOT operator to a binary sequence of any length. In that case, it will flip each bit of that sequence from 0 to 1 and from 1 to 0. Let’s look at an example:

$$\sim(01100100)_2 = (10011011)_2$$

Applications of bit manipulation#

Bit manipulation is a powerful tool for a programmer to have in their toolkit. There are plenty of numerous practical applications for bit manipulation.

Here are just a few examples:

• Bit manipulation can be used to optimize the performance or space of embedded systems
• The XOR operator (^) can be used to perform parity checks
• Bit operations are often used in data encryption and compression
  • For instance, the Advanced Encryption Standard (AES) uses bit operations
• Bits are used in networking to frame the packets of numerous bits, which are generally sent to another system through any kind of serial interface
• Digital image processors use bitwise operations to manipulate images

You can solve a wide variety of problems using just bits. With a little practice, you’ll be able to manipulate them quite easily.

Interviews#

Bit manipulation can be used to solve common programming challenges that can come up during technical interviews.

Some of these problems include:

• Checking for odd and even numbers in a sequence
• Counting set bits in an integer
• Multiplying two numbers using bitwise operators (Russian Peasant)
• Generating n-bit Gray codes
• Detecting if two integers have opposite signs
• Adding 1 to a given number

What to learn next#

That’s it for the basics of bit manipulation. Now that you’re familiar with the logic behind basic bit manipulation operators like OR, XOR, and NOT, you may want to start practicing these concepts in a more interactive setting.

Check out Grokking Bit Manipulation for Coding Interviews to learn how to solve problems using the bitwise operators covered in this article. Bit manipulation is a powerful technique that can be used to optimize your algorithmic and problem-solving skills.

Continue reading about computer science basics#

• Computer Number Systems 101: Binary & Hexadecimal Conversions
• Understand Bitwise AND (&) with JavaScript: 5-minute tutorial
• A quick guide to bit manipulation in Java