Bit Operations

Bit operations are very widely used, and there are many interview questions where they come handy. In this section we will cover bit operations and related techniques, and solve some problems using them.

Binary

All bit operations are usually used on integers in base 2 (binary) representation. You can first read about number bases in math section to learn how to convert to and from binary.

Be sure to be comfortable converting to and from binary by hand too. You can practice converting on these numbers:

Convert from binary:      Convert to binary:
–-------------------      ----------------
10010                     7
10                        18
111111                    23
101001                    5

Remember that each 1 bit represents a power of two. For example, 1011 = 8 + 2 + 1 = 11.

Operations

First, you need to be confident with bit operations. Here are the standard ones:

And

And operation on two bits is equal to 1 only when both bits are 1. In most programming languages, it's represented with & operator:

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

1001 & 1010 = 1000 (9 & 10 = 8)

Or

Or operation on two bits is equal to 1 when at least one of them is 1. In most programming languages, it's represented with | operator:

0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1

1001 | 1010 = 1011 (9 | 10 = 11)

Xor

Xor operation on two bits is equal to 1 when the bits are different. In most programming languages, it's represented with ^ operator:

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

1001 ^ 1010 = 0011 (9 ^ 10 = 3)

Specifically, x ^ x is always equal to 0.

Not

Not operation inverses the bit. In most programming languages, it's represented with ~ operator:

~0 = 1
~1 = 0

~1011 = 0100

If you are using a signed type like int, the first bit is often reserved for the negative numbers. Therefore not operation on integers may behave a bit differently from how you may expect. For more information on this read about how computers represent negative numbers and about two's complement.

final int N = 18;

System.out.println(N);  // 18
System.out.println(~N); // -19

System.out.println(Integer.toBinaryString(N));  // 10010
System.out.println(Integer.toBinaryString(~N)); // 11111111111111111111111111101101

Shift left

Shift left shifts all bits of the number several positions to the left. Shift left by one is equivalent to the multiplying the number by two (unless the number type overflows), while shift left by X positions is equivalent to the multiplying the number by 2^X. In most programming languages shift left is represented with << operator:

N << x (shift N left by x positions)

1001 << 1 = 10010   (9 << 1 = 9 * 2 = 18)
1001 << 3 = 1001000 (9 << 3 = 9 * 8 = 72)

Shift right

Shift right shifts all bits of the number several positions to the right. Shift right by one is equivalent to the integer division of the number by two, while shift right by X positions is equivalent to the integer division of the number by 2^X. In most programming languages shift right is represented with >> operator:

N >> x (shift N right by x positions)

1001 >> 1 = 100   (9 >> 1 = 9 / 2 = 4)
1001 >> 3 = 1     (9 >> 3 = 9 / 8 = 1)

Using bit operations

Let's learn some ways to practically use bit operations.

Getting a power of two

We can get Xth power of two by simply shifting 1 to the left (beware that for big powers it can overflow your number type):

1 << 3 = 1000 = 2^3 = 8
1 << 5 = 100000 = 2^5 = 32

Getting the Xth bit

We can get the Xth bit in the number as follows. First, recall that the Xth bit (starting from 0) represents 2^X. We get 2^X by shifting 1 by X positions to the left. After that, we AND our number with 2^X, and see if the result is bigger than zero. It is bigger only if the Xth bit is one:

int getBit(int n, int x) {
  return (n & (1 << x)) > 0 ? 1 : 0;
}

Setting the Xth bit to one

We can set the Xth bit to one very similarly. First, get 2^X by shifting. Then OR our number and 2^X – it will set the Xth bit to one (it may have already been one, in this case it will not change).

int setBit(int n, int x) {
  return (n | (1 << x));
}

Setting the Xth bit to zero

Setting the Xth bit to zero is a bit trickier. Let's first get 2^X, and then negate it – this will make a number with 1 bits in all positions except X. Then we can AND our number with this negated number to clear the Xth bit:

int clearBit(int n, int x) {
  return (n & ~(1 << x));
}

Toggle the Xth bit

To toggle the Xth bit (change it to 1 if it's 0, and to 0 if it's 1), we can XOR our number with 2^X. Can you see why it works?

int toggleBit(int n, int x) {
  return (n ^ (1 << x));
}

Problems with bit operations

Let's solve some problems with bit operations. Can you solve the following one?

The following problem can be smartly solved with bit operations. Can you figure it out?

Bitmasks

We can use binary numbers to represent choosing elements from the list. For example, if we have a list of N elements, we can represent which elements we choose from it with a binary number of length N. This binary number is often called bitmask in this case. In our bitmask, the Xth bit will be 1 if we take the Xth element, and 0 otherwise.

For example, let the list of size 5 be:

[apple, banana, pear, cherry, mango]

And let our bitmask be 10011.

10011 means we choose the 0th, 1st, and 4th element from the list (remember that in binary numbers the 0th bit is the last one). This corresponds to:

[apple, banana, mango]

We can translate this directly to the code:

int getBit(int n, int x) {
  return (n & (1 << x)) > 0 ? 1 : 0;
}

List<String> list = Arrays.asList("apple", "banana", "pear", "cherry", "mango");
        
final int bitMask = 19;
System.out.println(Integer.toBinaryString(bitMask)); // 10011

List<String> chosenElements = new ArrayList<>();
for (int i = 0; i < list.size(); i++)
    if (getBit(bitMask, i) == 1)
        chosenElements.add(list.get(i));

System.out.println(chosenElements); // [apple, banana, mango]

Now, try to solve the following problem with bitmasks:

More practice problems

Here are some more good problems to practice bit operations and bitmasks: