Bit manipulation is the direct manipulation of data bits to perform operations and is an important optimization skill now tested by FAANG recruiters. However, this topic is heavily mathematical and is rarely covered in a non-university computer science setting.

Today, we'll give you a tutorial on bit manipulation and explore some hands-on practice with popular interview questions.

Here’s what we’ll cover today:

• What is bit manipulation?
• Bitwise Operators
• Bitwise Tricks
• Hands-on practice with Bitwise operators
• What to learn next

Be ready for any bit manipulation question

Practice top asked questions for each bitwise operator with hands-on coding environments.

Master Solving Problems using Bit Manipulation

What is bit manipulation?

Bit manipulation is the process of applying logical operations on a sequence of bits, the smallest form of data in a computer, to achieve a required result. Bit manipulation has constant time complexity and process in parallel, meaning it is very efficient on all systems.

Most programming languages will have you work with abstractions, like objects or variables, rather than the bits they represent. However, direct bit manipulation is needed to improve performance and reduce error in certain situations.

Bit manipulation requires a strong knowledge of binary and binary conversion.

Here's a few examples of tasks that require bit manipulation:

• Low-level device control
• Error detection and correction algorithms
• Data compression
• Encryption algorithms
• Optimization

For example, take a look at the difference between an arithmetic and bit manipulation approach to finding the green portion of an RGB value:

// arithmetic
(rgb / 256) % 256

// bit
(rgb >> 8) & 0xFF

While both do the same thing, the second option is considerably faster, as it works directly within memory rather than through a level of abstraction.

We'll explore what each of these operators do later in this article (>> and &).

Bitwise Manipulation and Coding Interviews

Bit manipulation is also a common topic in coding interviews, especially with FAANG companies. These interviewers expect you to have a basic understanding of bits, fundamental bit operators, and generally understand the thought process behind bit manipulation.

Having this knowledge demonstrates that you're a well-rounded developer who understands both the specific tools and the foundation of computer science.

If you're applying for a role that will work with embedded systems or other low-level systems, you'll encounter more bit questions. In short, the closer your role is to machine level, the more bit manipulation questions you'll encounter.

The best way to prepare for bit manipulation questions is to practice using each bitwise operator and brush up on your binary to decimal conversions.

Bitwise Operators

Bitwise operations take one or more bit patterns or binary numerals and manipulate them at the bit level. They're essentially our tool to manipulate bits to achieve our operations.

While arithmetic operations perform operations on human-readable values (1+2), bitwise operators manipulate the low-level data directly.

Advantages

• They are fast and simple actions.
• They are directly supported by the processor.
• They are used to manipulate values for comparisons and calculations.
• Bitwise operations are incredibly simple and faster than arithmetic operations.

Let's take a quick look at each of the major Bitwise operators and their uses.

AND Operator

AND (&) is a binary operator that compares two operands of equal length. The operands are converted from their readable form to binary representation. For each bit, the operation checks if both bits are 1 across both operands. If yes, that bit is set to 1 in the answer. Otherwise, the corresponding result bit is set to 0.

It essentially multiplies each bit by the corresponding bit in the other operand. As multiplying anything by 0 results in 0, the AND comparison with any 0 bit will result in 0.

• If two input bits are 1, the output is 1.
• In all other cases its 0, for example:
  • 1 & 0 => yields to 0.
  • 0 & 1 => yields to 0.
  • 0 & 0 => yields to 0.

    0101 (decimal 5)
AND 0011 (decimal 3)

0 * 0 = 0

1 * 0 = 0

0 * 1 = 0

1 * 1 = 1

Therefore:

= 0001 (decimal 1)

The operation may be used to determine whether a particular bit is set (1) or clear (0). It's also used to clear selected bits of a register in which each bit represents an individual Boolean state.

class AndOperation {
    public static void main( String args[] ) {
        int x = 12;
        int y = 10;
        System.out.println("Bitwise AND of (" + x + " , " + y + ") is: " + (x & y)); // yields to 8
    }
}

OR Operator

The OR operator (|) is a binary operator that takes two equal-length operands but compares them in the opposite way to AND; if either corresponding bit is 1, the answer is 1. Otherwise, the answer will be 0. In other words, Bitwise OR returns ‘1’ if one of the inputs given is 1.

• If two input bits are 0, the output is 0.
• In all other cases, it is 1. For example:
  • 1 | 0 => yields to 1.
  • 0 | 1 => yields to 1.
  • 1 | 1 => yields to 1.

a = 12
b = 10
---------------------------------
a in Binary : 0000 0000 0000 1100
b in Binary : 0000 0000 0000 1010
---------------------------------
a | b           : 0000 0000 0000 1110
--------------------------------------

This is often used as an interim logic step for solving other problems.

class OROperation {
    private static int helper(int x, int y) {
        return x | y;
    }
    public static void main(String[] args) {
        int x = 12;
        int y = 10;
        System.out.println("Bitwise OR of " + x + ", " + y + " is: " + helper(x, y)); // yields to 14
    }
}

NOT Operator

NOT (~), or sometimes called the bitwise complement operator, is a unary operation that takes a single input and swaps each bit in its binary representation to the opposite value.

All instances of 0 become 1, and all instances of 1 become 0. In other words, NOT inverts each input bit. This inverted sequence is called the one's complement of a bit series.

For example, consider x = 1

The binary number representation of x is:

x = 00000000 00000000 00000000 00000001

Now, Bitwise NOT of x will be:

~x = 11111111 11111111 11111111 11111110

So:

• x contains 31 zeros(0's) and one 1
• ~x contains 31 ones(1's) and one 0(zero)

This makes the number negative as any bit collection that starts with 1 is negative.

NOT is useful for flipping unsigned numbers to the mirrored value on the opposite side of their mid-point.

For 8-bit unsigned integers, NOT x = 255 - x.

Formula: ~x = 2^{32} - x

class NOTOperation {
    public static void main( String args[] ) {
        int a = 1;
        System.out.println("Bitwise NOT of a is : " + ~a);
    }
}

XOR Operator

The bitwise XOR operation (^), short for "Exclusive-Or", is a binary operator that takes two input arguments and compares each corresponding bit. If the bits are opposite, the result has a 1 in that bit position. If they match, a 0 is returned.

• 1 ^ 1 => yields to 0.
• 0 ^ 0 => yields to 0.
• 1 ^ 0 => yields to 1.
• 0 ^ 1 => yields to 1.

For example:

a = 12
b = 10
--------------------------------------
a in binary : 0000 0000 0000 1100
b in binary : 0000 0000 0000 1010
--------------------------------------
a ^ b       : 0000 0000 0000 0110
--------------------------------------

XOR is used to invert selected individual bits in a register or manipulate bit patterns that represent Boolean states.

XOR is also sometimes used to set the value of a registry to zero as XOR with two of the same input will always result in 0.

class XOROperation {
    public static void main( String args[] ) {
        int x = 12;
        int y = 10;
        System.out.println("Bitwise XOR of (x , y) is : " + (x ^ y)); // yields to 6
    }
}

Left and right shift operator

​
A bit shift is a Bitwise operation where the order of a series of bits is moved to efficiently perform a mathematical operation. A bit shift moves each digit in a number’s binary representation left or right by a number of spaces specified by the second operand.

These operators can be applied to integral types such as int, long, short, byte, or char.

There are three types of shift:

• Left shift: << is the left shift operator and meets both logical and arithmetic shifts’ needs.
• Arithmetic/signed right shift: >> is the arithmetic (or signed) right shift operator.
• Logical/unsigned right shift: >>> is the logical (or unsigned) right shift operator.

In Java, all integer data types are signed and << and >> are solely arithmetic shifts.

Here's an example of a left shift:

6 = 00000000 00000000 00000000 00000110

Shifting this bit pattern to the left one position (6 << 1) results in the number 12:

6 << 1 = 00000000 00000000 00000000 00001100

As you can see, the digits have shifted to the left by one position, and the last digit on the right is filled with a zero. Note that shifting left is equivalent to multiplication by powers of 2.

6 << 1 → 6 * 2^1 → 6 * 2

6 << 3 → 6 * 2^3 → 6 * 8

Well-optimized compilers will use this rule to replace multiplication with shifts whenever possible, as shifts are faster.

class LeftShift {
    private static int helper(int number, int i) {
        return number << i;// multiplies `number` with 2^i times.
    }
    public static void main(String[] args) {
        int number = 100;
        System.out.println(number + " shifted 1 position left, yields to " + helper(number, 1));
        System.out.println(number + " shifted 2 positions left, yields to " + helper(number, 2));
        System.out.println(number + " shifted 3 positions left, yields to " + helper(number, 3));
        System.out.println(number + " shifted 4 positions left, yields to " + helper(number, 4));
    }
}

With right shift, you can either do arithmetic (>>) or logical (>>) shift.

The difference is that arithmetic shifts maintain the same most significant bit (MSB) or sign bit, the leftmost bit which determines if a number is positive or negative.

1011 0101 >> 1 = **1**101 1010

Formula: x >> y = x/(2^y)

On the other hand, a logical shift simply moves everything to the right and replaces the MSB with a 0.

1011 0101 >>> 1 = 0101 1010

Formula: a >>> b = a/(2^b)

Keep learning bit manipulation.

Prepare for FAANG bit manipulation questions in half the time. Educative's interview prep courses let you set yourself up for success with hands-on practice with the most asked interview questions.

Master Solving Problems using Bit Manipulation

Bitwise Tricks

Now, let's look at a few tricks you can do using bitwise operators.

These are often used as interview questions to check if you've reviewed basic bit manipulation and can apply it to day-to-day coding tasks.

Check if a number is even

This one tests your knowledge of how AND works and how even/odd numbers differ in binary. You can simply use:

(x & 1 ) == 0
  0110 (6)
& 0001
= 0000 TRUE

This solution relies on two things:

• 2 equates to 0001
• The rightmost number for all odd numbers greater than 2 is 1

Any time the final bit evaluates to 1, you know that it matched and is, therefore, an odd number. If it instead evaluates to 0, you know that no numbers matched and therefore it's even.

Convert characters to uppercase or lowercase

This trick tests your knowledge of uppercase and lowercase characters in binary. You can convert any character, ch, to the opposite case using ch ^= 32.

This is because the binary representation of lowercase and uppercase letters are nearly identical, with only 1 bit of difference.

Using the XOR operation lets us toggle that single bit and swap it to the opposite value, therefore making a lowercase character uppercase or vice versa.

public class Test 
{ 

    static int x=32; 

    // tOGGLE cASE = swaps CAPS to lower 
    // case and lower case to CAPS 
    static String toggleCase(char[] a) 
    { 
        for (int i=0; i<a.length; i++) { 

            // Bitwise XOR with 32 
            a[i]^=32; 
        } 
        return new String(a); 
    } 

    /* Driver program */
    public static void main(String[] args)  
    { 
        String str = "CheRrY"; 
        System.out.print("Toggle case: "); 
        str = toggleCase(str.toCharArray()); 
        System.out.println(str); 

        System.out.print("Original string: "); 
        str = toggleCase(str.toCharArray()); 
        System.out.println(str);     
    } 
} 

Hands-on practice with Bitwise Operators

​
Now, let's have some hands-on practice with these operators.

AND Challenge: Count set bits

Write a Java program to count the number of bits set to 1 (set bits) of an integer.

Solution and Explanation

class CountSetBit {
    private static int helper(int n) {
        int count = 0;
        while (n > 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int number = 125;
        System.out.println("SetBit Count is : " + helper(number));
    }
}

In this approach, we count only the set bits. So,

• If a number has 2 set bits, then the while loop runs two times.
• If a number has 4 set bits, then the while loop runs four times.

Our while loop iterates until n = 0, dividing by 2 each time via the AND operator. On pass 1, 125 becomes 62, and count increases by 1. On the second pass, 62 becomes 31, and the count increases to 2. This continues until n becomes 0 and the count is then returned.

Bitwise OR: Number of Flips

Write a program that takes 3 integers and uses the lowest number of flips to make the sum of the first two numbers equal to the third. The program will return the number of flips required.

A flip is changing one single bit to the opposite value ie. 1 --> 0 or 0 --> 1.

Input: a = 2, b = 6, c = 5

Output: 3

Solution and Explanation

class MinFlips {
    private static int helper(int a, int b, int c) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int bitC = ((c >> i) & 1);
            int bitA = ((a >> i) & 1);
            int bitB = ((b >> i) & 1);

            if ((bitA | bitB) != bitC) {
                ans += (bitC == 0) ? (bitA == 1 && bitB == 1) ? 2 : 1 : 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int a = 2;
        int b = 6;
        int c = 5;
        System.out.println("Min Flips required to make two numbers equal to third is : " + helper(a, b, c));
    }
}

First, we initialize ans to 0. Then we loop through from a range of 0 - 31. We initialize bitA, bitB, and bitC to equal our right shift formula ANDed with 1:

(a/(2^i) & 1

Then, we check if bitA | bitB equals bitC. If yes, we move on to check if bitC = 0. From there, if bitA = 1 and bitB = 1 then we increase ans by 2. Otherwise, we increase ans by 1.

Finally, we return ans, which has increased by one on every operation.

Bitwise XOR: Single Number

Find the element in an array that is not repeated.

Input: nums = { 4, 1, 2, 9, 1, 4, 2 }

Output: 9

Solution and Explanation

class SingleNumber {
    private static int singleNumber(int[] nums) {
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        return xor;
    }

    public static void main(String[] args) {
        int[] nums = {4, 1, 2, 9, 1, 4, 2};
        System.out.println("Element appearing one time is " + singleNumber(nums));
    }
}

This solution relies on the following logic:

• If we take XOR of zero and some bit, it will return that bit: a ^ 0 = a
• If we take XOR of two same bits, it will return 0: a ^ a = 0
• For n numbers, the below math can be applied: a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

For example,

1 ^ 5 ^ 1 =

(1 ^ 1) ^ 5 =

0 ^ 5 = 5

Therefore, we can XOR all bits together to find the unique number.

Bitwise Left Shift: Get First Set Bit

Given an integer, find the position of the first set-bit (1) from the right.

Input: n = 18

18 in binary = 0b10010

Output: 2

Solution and Explanation

class FirstSetBitPosition {
    private static int helper(int n) {
        if (n == 0) {
            return 0;
        }

        int k = 1;

        while (true) {
            if ((n & (1 << (k - 1))) == 0) {
                k++;
            } else {
                return k;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("First setbit position for number: 18 is -> " + helper(18));
        System.out.println("First setbit position for number: 5 is -> " + helper(5));
        System.out.println("First setbit position for number: 32 is -> " + helper(32));
    }
}

The logic of this solution relies on a combination of left shifting and the AND operation.

Essentially, we first check if the rightmost significant bit is the set bet using bit & 1. If not, we keep shifting left and checking until we find the bit that makes our AND operation yield 1.

The number of shifts is tracked by our pointer, k. Once we do find the set bit, we return k as our answer.

What to learn next

Congratulations on finishing our bit manipulation quick guide! Bit manipulation can be a tricky topic to learn, but hands-on practice is the best way to improve.

As you look for more practice, check out these practice problems:

• Find the missing number
• Find the first set bit using right shifting
• Count the number of digits in an integer
• Check if a number is a power of 2

To help you practice these and other bit manipulation interview questions, Educative has created Master Solving Problems using Bit Manipulation. This course will help you refresh your knowledge of binary conversions as well as tons of hands-on interview question practice.

By the end of the course, you'll know efficient solutions to all the top bit manipulation interview questions asked by FAANG recruiters.

Happy learning!

Continue reading about number systems

• Big-O Notation Cheat Sheet: quick answers to Big-O questions
• Computer Number Systems 101: Binary & Hexadecimal Conversions
• Top Data Structures and Algorithms every developer must know