Is bit manipulation important for an interview?

You should have a thorough grasp of binary representation in computer systems before your interview. Proficiency in bit manipulation is crucial if you develop embedded systems. This will help you in the embedded system interview processes.

Home/Blog/Programming/A quick guide to bitwise operators in Java

A quick guide to bitwise operators in Java

Ryan Thelin

Nov 20, 2023

12 min read

content

What is bit manipulation?Bitwise Manipulation and Coding Interviews Bitwise Operators AND Operator OR Operator NOT Operator XOR Operator Left and right shift operator Keep learning bit manipulation.Bitwise Tricks Check if a number is even Convert characters to uppercase or lowercase Hands-on practice with Bitwise Operators AND Challenge: Count set bits Bitwise OR: Number of Flips Bitwise XOR: Single Number Bitwise Left Shift: Get First Set Bit What to learn next Continue reading about number systems

Become a Software Engineer in Months, Not Years

From your first line of code, to your first day on the job — Educative has you covered. Join 2M+ developers learning in-demand programming skills.

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

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:

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.

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.

Enjoying the article? Scroll down to sign up for our free, bi-monthly newsletter.

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.

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.

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$ .

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.

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 =$ $1101$ $1010$ .

Formula: $x >> y = \frac{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 = \frac{a}{2^b}$

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);     
    } 
}

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:

$( \frac{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

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#

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

A quick guide to bitwise operators in Java

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