Bit Manipulation (Complete Guide)

What is Bit Manipulation?

Bit Manipulation is a collection of techniques that allows us to solve various problems by leveraging the binary representation of a number and its bits. Here, in this article, some interesting bit manipulation techniques and algorithms are described below:

Check if a number is a power of 2:

A nice Bit Manipulation based approach to solve this problem is to observe the fact that all powers of two have only 1 bit (MSB) set in their binary representation. So, when we subtract 1 from any power of 2, the set bit gets unset, and all the bits coming after it, gets set. Performing the bitwise AND of these two numbers, we should get the result as zero, if the original number was a power of 2.

An edge case to consider in this approach is that this approach will not work if n = 0, so we need to handle this case separately.

C++ Code

bool checkIfPowerOf2(int n) {
  n = abs(n);
  return n && (!(n & (n - 1)));
}

Java Code

public static boolean checkIfPowerOf2(int n) {
  n = Math.abs(n);
  return (n > 0) && (((n & (n - 1)) == 0));
}

Python Code

def checkIfPowerOf2(n):
    n = abs(n)
    return n and (not (n & (n - 1)))

Complexity Analysis

• Time Complexity: O(1)
• Space Complexity: O(1)

Swapping 2 Numbers using Bitwise Operators:

We can swap 2 numbers without using the 3rd variable, by using the bitwise XOR operator.  Note that the bitwise XOR of 2 numbers returns a number that has those bits set, which are unset in one of the numbers and set in the other number. Using this number, if XOR it with our original numbers in reverse order, we will be able to recover back our original numbers, but now in swapped condition.

C++ Implementation

void swap(int &a, int &b) {
    cout << "Before Swapping:" << endl;
    cout << a << " " << b << endl;
    a ^= b;
    b ^= a;
    a ^= b;
    cout << "After Swapping:" << endl;
    cout << a << " " << b << endl;

Java Implementation

public static void swap(int a, int b) {
        System.out.println("Before Swapping:");
        System.out.println(a + " " + b);
        a ^= b;
        b ^= a;
        a ^= b;
        System.out.println("After Swapping:");
        System.out.println(a + " " + b);
    }

Python Implementation

def swap(a, b):
    print("Before Swapping:")
    print(a, b)
    a ^= b
    b ^= a
    a ^= b
    print("After Swapping:")
    print(a, b)

Complexity Analysis

• Time Complexity: O(1)
• Space Complexity: O(1)

XOR of numbers from [1, n]:

The XOR of all numbers in the range [1, n] can be efficiently calculated using the following formula:

• If n % 4 = 0, the answer is n.
• If n % 4 = 1, the answer is 1.
• If n % 4 = 2, the answer is n + 1.
• If n % 4 = 3, the answer is 0.

This formula can be observed by brute-forcing the answers for some small n and then finding the pattern in the answers.

C++ Code

int getXOR(int n) {
    if(n % 4 == 0) {
        return n;
    }
    else if(n % 4 == 1) {
        return 1;
    }
    else if(n % 4 == 2) {
        return ++n;
    }
    else {
        return 0;
    }
}

Java Code

public static int getXOR(int n) {
        if(n % 4 == 0) {
            return n;
        }
        else if(n % 4 == 1) {
            return 1;
        }
        else if(n % 4 == 2) {
            return ++n;
        }
        else {
            return 0;
        }
    }

Python Code

def getXOR(n):
    if n % 4 == 0:
        return n
    elif n % 4 == 1:
        return 1
    elif n % 4 == 2:
        return n + 1
    else:
        return 0

Complexity Analysis

• Time Complexity: O(1)
• Space Complexity: O(1)

Finding the MSB in a Fixed-Size Integer

Suppose that we are dealing with 32-bit integers. The approach here is to set all the bits of the number, and then add 1 to it, so that only a bit, which appears after the MSB is set. Then we can just divide the number by 2, and return the answer.

C++ Implementation

int setBit(int n) {
  n |= (n >> 1);
  n |= (n >> 2);
  n |= (n >> 4);
  n |= (n >> 8);
  n |= (n >> 16);
  n++;
  n >>= 1;
  return n;

Java Implementation

public static int setBit(int n) {
  n |= (n >> 1);
  n |= (n >> 2);
  n |= (n >> 4);
  n |= (n >> 8);
  n |= (n >> 16);
  n++;
  n >>= 1;
  return n;
}

Python Implementation

def setBit(n):
    n |= (n >> 1);
    n |= (n >> 2);
    n |= (n >> 4);
    n |= (n >> 8);
    n |= (n >> 16);
    n += 1;
    n >>= 1;
    return n;

Complexity Analysis

• Time Complexity: O(1)
• Space Complexity: O(1)

FAQs

Q. What is meant by a bit being set or unset?
A. If a bit has value 1, it is said to be set, else it is said to be unset.

Q. How many bits are present in a number’s binary representation?
A. floor(log₂n) + 1 bits are present in a number’s binary representation.