Year-End Discount: 10% OFF 1-year and 20% OFF 2-year subscriptions!

Home/Blog/The basics of bit manipulation

The basics of bit manipulation

Oct 11, 2022 - 8 min read
Faisal Aslam
editor-page-cover

You might be wondering why learning bit manipulation is important. After all, most developers never have to write code that manipulates bits directly. However, bit manipulation is a fundamental concept in computer science, and many algorithms and data structures can be expressed more elegantly (and sometimes more efficiently) using bitwise operations. In addition, bit manipulation questions are often asked in technical interviews as a way to test a candidate’s knowledge of low-level details and their ability to think creatively.

This tutorial is intended to introduce bit manipulation for programmers and students. We’ll also go over how to convert binary sequences to base 10, bit manipulation operators, and the logic behind those operators.

We’ll cover:

Get hands-on with bit manipulation today.

Try one of our 400+ courses and learning paths: Grokking Bit Manipulation for Coding Interviews.

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 0th0^{th} bit and the right-most bit as the nthn^{th} bit.

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

Here’s an example.

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

Solution:

(1×23)+(0×22)+(1×21)+(1×20)=8+2+1=(11)10(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:

X Y X&Y
00 00 00
00 11 00
11 00 00
11 11 11

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 XX and YY, where

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

Let’s find X&YX\&Y.

X Y X&Y
10101010 10011001 10001000

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

The result of the

  • Rightmost pair is 0&1=00\&1=0
  • Second pair from the right is 1&0=01\& 0=0
  • Third pair is 0&0=00\&0=0
  • Leftmost pair is 1&1=11\& 1=1

Hence, our result will be (1000)2=8(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.

X Y X|Y
00 00 00
00 11 11
11 00 11
11 11 11

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 XX and YY, where

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

Let’s find XYX | Y.

X Y X|Y
10101010 10011001 10111011

Solution: XY=(1010)2X | Y = (1010)_2 | (1001)2=(1011)2=(11)10(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.

X Y X ^ Y
00 00 00
00 11 11
11 00 11
11 11 00

Let’s try an example:

X XOR Y=(1010)2 XOR (1001)2=(0011)2=3X \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.

X ~X
11 00
00 11

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:

(01100100)2=(10011011)2\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


WRITTEN BYFaisal Aslam

Join a community of more than 1.6 million readers. A free, bi-monthly email with a roundup of Educative's top articles and coding tips.