Bit Manipulation Basics

Every number inside a computer is really just a row of 0s and 1s. We call each of those 0s and 1s a bit, which is short for binary digit. Most of the time you never see those bits. You write 5 and the machine quietly stores it as 101. But sometimes you want to reach in and work on those bits directly. That is what bit manipulation is.

Here is the pain. Say you want to check if a number is even or odd. The normal way uses the remainder. That works. But the computer has to do a division to find the remainder, and division is slow. With bits you can answer the same question by looking at just one bit. It is faster. And it is one short line. So bit manipulation gives you small tricks that run very fast.

In this tutorial we go slow. We define each operator. We show a tiny example. Then we build up the common tricks.

📚 What Is a Bit, Really?

A number in binary is written using only 0 and 1. Each spot in that row is a bit. The rightmost bit is the smallest. Each bit to the left is worth twice as much as the one before it.

Take the number 13. In binary it is 1101. Read it like this.

Add up the spots that have a 1. That is 8 plus 4 plus 1, which gives 13. So 1101 is 13. Good. Now that we can read bits, let us meet the operators that work on them.

🔧 The Bitwise Operators

A bitwise operator is an operator that works on two numbers bit by bit. It lines up the bits of both numbers and decides each result bit on its own. There are a few of them. Each one is simple once you see its little table.

AND (&)

AND looks at one bit from each number. The result bit is 1 only when both input bits are 1. Otherwise it is 0. Think of it as “both must agree.”

So 6 & 3 lines up 110 and 011. Only the middle bit is 1 in both. The answer is 010, which is 2.

OR (|)

OR gives 1 when at least one of the two bits is 1. It only gives 0 when both are 0. Think of it as “either one is enough.”

So 6 | 1 lines up 110 and 001. Every spot has at least one 1. The answer comes out 111, which is 7.

XOR (^)

XOR gives 1 when the two bits are different. If they are the same, you get 0. Think of it as “spot the difference.”

So 6 ^ 3 lines up 110 and 011. The first and last spots differ. The middle is the same. The answer is 101, which is 5.

NOT (~)

NOT works on just one number. It flips every bit. Every 1 becomes 0 and every 0 becomes 1. Because of how computers store negative numbers, ~x ends up equal to -x - 1. So ~5 is -6. That feels strange at first. But it is just every bit flipped.

Left shift (<<) and right shift (>>)

A shift moves all the bits a number of places to the left or to the right.

Left shift moves the bits to the left and fills the empty spots on the right with 0. Each move to the left doubles the number. So 3 shifted left by 1 becomes 6. Shift it by 2 and you get 12.

Right shift moves the bits to the right and drops the bits that fall off the end. Each move to the right halves the number. It throws away any remainder. So 13 shifted right by 1 becomes 6.

🎯 Common Bit Tricks

Now the fun part. These are small recipes you will reuse a lot.

The trick to most of them is a mask. A mask is just a number you build with a 1 in the exact spot you care about, and 0s everywhere else. You make a mask for position i by writing 1 << i, which is the number 1 shifted left i times.

Here is what we will do, in plain words first.

• Check if a number is even or odd. Look at the last bit. If the last bit is 0 the number is even. If it is 1 it is odd. We test it with n & 1.
• Multiply by 2. Shift left by 1, so n << 1.
• Divide by 2. Shift right by 1, so n >> 1.
• Check if a bit is set. “Set” means the bit is 1. We make a mask for that spot and AND it with the number. If the result is not 0, the bit was 1.
• Set a bit. Force a chosen bit to 1. We OR the number with the mask.
• Clear a bit. Force a chosen bit to 0. We AND the number with a flipped mask.

🧪 Steps to Use These Tricks in Code

Let us put every trick into one small program so you can see the output.

Here is the plan the code follows.

1. Start with the number 13, which is 1101 in bits.
2. Show AND, OR, and XOR of two numbers.
3. Check if 13 is odd by testing its last bit.
4. Double it with a left shift. Halve it with a right shift.
5. Check whether bit 2 is set in 13. Look at 1101 from the right, counting from 0. Bit 2 is a 1, so it is set.
6. Set bit 1 to turn 13 into 15.
7. Clear bit 0 to turn 13 into 12.

#include <stdio.h>

int main(void) {
    int n = 13; // 1101 in binary

    // Basic operators
    printf("6 & 3 = %d\n", 6 & 3); // AND
    printf("6 | 1 = %d\n", 6 | 1); // OR
    printf("6 ^ 3 = %d\n", 6 ^ 3); // XOR

    // Even or odd: look at the last bit
    if ((n & 1) == 1)
        printf("%d is odd\n", n);
    else
        printf("%d is even\n", n);

    // Multiply and divide by 2 using shifts
    printf("n times 2 = %d\n", n << 1);
    printf("n divided by 2 = %d\n", n >> 1);

    // Check if bit 2 is set
    int i = 2;
    if ((n & (1 << i)) != 0)
        printf("bit %d is set\n", i);
    else
        printf("bit %d is not set\n", i);

    // Set bit 1 (13 -> 15)
    printf("set bit 1 = %d\n", n | (1 << 1));

    // Clear bit 0 (13 -> 12)
    printf("clear bit 0 = %d\n", n & ~(1 << 0));

    return 0;
}

6 & 3 = 2
6 | 1 = 7
6 ^ 3 = 5
13 is odd
n times 2 = 26
n divided by 2 = 6
bit 2 is set
set bit 1 = 15
clear bit 0 = 12

#include <iostream>
using namespace std;

int main() {
    int n = 13; // 1101 in binary

    // Basic operators
    cout << "6 & 3 = " << (6 & 3) << endl; // AND
    cout << "6 | 1 = " << (6 | 1) << endl; // OR
    cout << "6 ^ 3 = " << (6 ^ 3) << endl; // XOR

    // Even or odd: look at the last bit
    if ((n & 1) == 1)
        cout << n << " is odd" << endl;
    else
        cout << n << " is even" << endl;

    // Multiply and divide by 2 using shifts
    cout << "n times 2 = " << (n << 1) << endl;
    cout << "n divided by 2 = " << (n >> 1) << endl;

    // Check if bit 2 is set
    int i = 2;
    if ((n & (1 << i)) != 0)
        cout << "bit " << i << " is set" << endl;
    else
        cout << "bit " << i << " is not set" << endl;

    // Set bit 1 (13 -> 15)
    cout << "set bit 1 = " << (n | (1 << 1)) << endl;

    // Clear bit 0 (13 -> 12)
    cout << "clear bit 0 = " << (n & ~(1 << 0)) << endl;

    return 0;
}

6 & 3 = 2
6 | 1 = 7
6 ^ 3 = 5
13 is odd
n times 2 = 26
n divided by 2 = 6
bit 2 is set
set bit 1 = 15
clear bit 0 = 12

public class BitTricks {
    public static void main(String[] args) {
        int n = 13; // 1101 in binary

        // Basic operators
        System.out.println("6 & 3 = " + (6 & 3)); // AND
        System.out.println("6 | 1 = " + (6 | 1)); // OR
        System.out.println("6 ^ 3 = " + (6 ^ 3)); // XOR

        // Even or odd: look at the last bit
        if ((n & 1) == 1)
            System.out.println(n + " is odd");
        else
            System.out.println(n + " is even");

        // Multiply and divide by 2 using shifts
        System.out.println("n times 2 = " + (n << 1));
        System.out.println("n divided by 2 = " + (n >> 1));

        // Check if bit 2 is set
        int i = 2;
        if ((n & (1 << i)) != 0)
            System.out.println("bit " + i + " is set");
        else
            System.out.println("bit " + i + " is not set");

        // Set bit 1 (13 -> 15)
        System.out.println("set bit 1 = " + (n | (1 << 1)));

        // Clear bit 0 (13 -> 12)
        System.out.println("clear bit 0 = " + (n & ~(1 << 0)));
    }
}

6 & 3 = 2
6 | 1 = 7
6 ^ 3 = 5
13 is odd
n times 2 = 26
n divided by 2 = 6
bit 2 is set
set bit 1 = 15
clear bit 0 = 12

def main():
    n = 13  # 1101 in binary

    # Basic operators
    print("6 & 3 =", 6 & 3)  # AND
    print("6 | 1 =", 6 | 1)  # OR
    print("6 ^ 3 =", 6 ^ 3)  # XOR

    # Even or odd: look at the last bit
    if (n & 1) == 1:
        print(n, "is odd")
    else:
        print(n, "is even")

    # Multiply and divide by 2 using shifts
    print("n times 2 =", n << 1)
    print("n divided by 2 =", n >> 1)

    # Check if bit 2 is set
    i = 2
    if (n & (1 << i)) != 0:
        print("bit", i, "is set")
    else:
        print("bit", i, "is not set")

    # Set bit 1 (13 -> 15)
    print("set bit 1 =", n | (1 << 1))

    # Clear bit 0 (13 -> 12)
    print("clear bit 0 =", n & ~(1 << 0))


main()

6 & 3 = 2
6 | 1 = 7
6 ^ 3 = 5
13 is odd
n times 2 = 26
n divided by 2 = 6
bit 2 is set
set bit 1 = 15
clear bit 0 = 12

function main() {
  const n = 13; // 1101 in binary

  // Basic operators
  console.log("6 & 3 =", 6 & 3); // AND
  console.log("6 | 1 =", 6 | 1); // OR
  console.log("6 ^ 3 =", 6 ^ 3); // XOR

  // Even or odd: look at the last bit
  if ((n & 1) === 1) {
    console.log(n + " is odd");
  } else {
    console.log(n + " is even");
  }

  // Multiply and divide by 2 using shifts
  console.log("n times 2 =", n << 1);
  console.log("n divided by 2 =", n >> 1);

  // Check if bit 2 is set
  const i = 2;
  if ((n & (1 << i)) !== 0) {
    console.log("bit " + i + " is set");
  } else {
    console.log("bit " + i + " is not set");
  }

  // Set bit 1 (13 -> 15)
  console.log("set bit 1 =", n | (1 << 1));

  // Clear bit 0 (13 -> 12)
  console.log("clear bit 0 =", n & ~(1 << 0));
}

main();

6 & 3 = 2
6 | 1 = 7
6 ^ 3 = 5
13 is odd
n times 2 = 26
n divided by 2 = 6
bit 2 is set
set bit 1 = 15
clear bit 0 = 12

📊 Quick Reference Table

Here are the tricks side by side so you can copy the right one when you need it.

⚠️ Common Mistakes

A few traps catch almost everyone at the start. Watch out for these.

• Mixing up & and &&. The single & is the bitwise operator that works on bits. The double && is the logical AND that works on true and false. Same idea, different jobs. The same warning goes for | and ||.
• Forgetting that operators have low priority. In many languages & runs after comparison. So n & 1 == 0 is read as n & (1 == 0), which is wrong. Wrap your bit test in parentheses, like (n & 1) == 0.
• Expecting ~5 to be 5 with the sign removed. NOT flips every bit, so ~5 is -6, not -5. That surprises people.
• Shifting too far. Shifting a number left by more bits than it can hold gives a result you did not expect. Keep shift amounts small and sensible.
• Thinking right shift keeps the remainder. It does not. 13 >> 1 is 6, not 6.5. The dropped bit is gone.

🧩 What You’ve Learned

✅ A bit is one 0 or 1, and every number is just a row of bits.

✅ AND keeps a bit only when both are 1, OR keeps it when either is 1, and XOR keeps it when the two differ.

✅ NOT flips every bit, so ~x comes out as -x - 1.

✅ Left shift doubles a number and right shift halves it.

✅ You can check, set, and clear any bit using a mask built with 1 << i.

✅ Every one of these tricks runs in O(1) constant time.

🚀 What’s Next?

You now have a handy set of fast bit tricks. Next, keep building your core problem-solving toolkit.

• Recursion
• Big O Notation