A Guide To Master Bit Manipulation For Coding Interviews

You can find the complete Bit manipulation tutorial on my website for FREE.

🚀 https://www.ggorantala.dev/all-courses/.

This article will teach you the basics of the number system and bitwise operators.

Please check out my free course for detailed explanations, sketches, illustrations, and coding interview problems in 5 different languages, including C++, Java, Python, JavaScript, and TypeScript.

Number system

A number system is a writing system where digits and symbols are used consistently to represent values.

The exact sequence of symbols may represent different numbers in different number systems.

Mathematics has various types of number systems, like binary, decimal, octal, and hexadecimal.

Of all these number systems, decimal and binary are the most important for bit manipulation.

What is the binary number system?

Another number system that became famous after the decimal is the binary number system, which has only two digits, 0 and 1.

If a number system has n digits, we say that the base of the number system is n. So, the binary number system can also be called the base-2 number system.

Representation

For example, 125 can be represented as 01111101 in the computer binary system. Anything in computer language gets converted into a binary number system.

What do binary numbers represent?

In mathematics and digital electronics:

• A binary number is expressed in the base-2 or binary number system.
• It uses only two symbols: typically “0” (zero) and “1” (one). The base-2 number system is a positional notation with a radix of 2. Each digit is referred to as a bit.

Binary counting

Binary counting follows the same procedure, except only the symbols 0 and 1 are available. Thus, after a digit reaches 1 in binary, an increment resets it to 0 but also causes an increment of the next digit to the left.

0000,

0001, (rightmost digit starts over, and next digit is incremented)

0010, 0011, (rightmost two digits start over, and next digit is incremented)

0100, 0101, 0110, 0111, (rightmost three digits start over, and the next digit is incremented)

1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111,…

Binary to decimal conversion

In the binary system, each digit represents an increasing power of 2, with the rightmost digit representing 2⁰, the next representing 2¹, then 2², and so on. The value of a binary number is the sum of the powers of 2 represented by each “1” digit. For example, the binary number 100101 is converted to decimal form as follows:

100101₂ = [ ( 1 ) x 2⁵ ] + [ ( 0 ) x 2⁴ ] + [ ( 0 ) x 2³ ] + [ ( 1 ) x 2² ] + [ ( 0 ) x 2¹ ] + [ ( 1 ) x 2⁰ ]

100101₂ = [ ( 1 ) x 32 ] + [ ( 0 ) x 16 ] + [ ( 0 ) x 8 ] + [ ( 1 ) x 4 ] + [ ( 0 ) x 2 ] + [ ( 1 ) x 0 ]

100101₂ = 37₁₀

Bitwise Operators

In computer programming, a Bitwise operation operates on one or more bit patterns or binary numerals at the bit level.

• They are fast and simple actions.
• The processor directly supports them.
• They are used to manipulate values for comparisons and calculations.
• Bitwise operations are incredibly simple and faster than arithmetic operations.

Bitwise algorithms are used to perform operations at the bit level or to manipulate bits in different ways.

Bitwise operations are much faster and are sometimes used to improve the efficiency of a program.

Any indication of a bit’s position is counted from the right (least significant) side to the left.

Bitwise AND

Bitwise AND is the most commonly used logical Bitwise operator. It is represented by a sign (&).

AND operator is the same as the AND gate we studied in the chapter on digital electronics, as shown below:

The Bitwise AND operator is denoted by &. When an AND gate is given with two inputs, the corresponding output will be:

If two input bits are 1, the output is 1.
In all other cases, it's 0. For example
1 & 0 => yields to 0.
0 & 1 => yields to 0.
0 & 0 => yields to 0.

Let us visualize the steps in detail:

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

// Outputs: Bitwise AND of (12 , 10) is: 8

Bitwise OR

Bitwise OR is the most commonly used logical Bitwise operator. It is represented by a sign (|).

OR operator is the same as the OR gate we studied in the chapter on digital electronics, as shown below:

The Bitwise OR operator is denoted by |. When an OR gate is given with two inputs, the corresponding outputs will be:

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.
So, Bitwise OR returns 1 if one of the inputs given is 1.

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

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

// Output : Bitwise OR of 12, 10 is: 14

Bitwise NOT

This introduces the tilde '~' character. This is applied to a single operand and inverts each input operand's bit. This is the same as the NOT gate we studied in the digital electronics chapter shown below:

We already discussed the NOT operator and how it inverts each input bit.

Now let’s see in-depth how to represent the output of each input and its decimal equivalent.

As the name suggests, it takes the input number, considers its binary representation, and inverts every bit, which means the 0 bit becomes 1, and the 1 bit becomes 0.

Example:
Let’s consider x = 1;

The binary representation of x as follows:

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)
  So, how do we calculate the value of this? It is tough since we have 31 ones and 1 zero.

• To guess the value, we must know how signed numbers are stored in a programming language.

• Since we know Java integers have the range from -2^31 to 2^31-1, or -2,147,483,648 to 2,147,483,647.
  In Java, positive numbers are stored by doing decimal to binary conversion.

For example, if we have the decimal number 3, then the binary is 11 with 30 0's on the left side. Nevertheless, negative numbers are stored in 2’s complement.

What is 2’s complement?

The rule of 2’s complement is:

1. If the leading bit on the left side is 0, then it is a positive number.
2. If the leading bit on the left side is 1, then it is a negative number.
3. When doing NOT operation on positive numbers, they become negative and vice-versa. Now, 2’s complement representation is

If we were given a negative number “-x”, its 2’s complement representation is "2^32 - x".

Formula

~x=(2^32 - x)

a =  1 => in Binary : 0000 0000 0000 0001

        ~a in Binary : 1111 1111 1111 1110
 ----------------------------------------

So,  a = 1 becomes -2(~a)

I can't give many details about 2's compliment here as this article size will last longer. The course explains everything.

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

//Output : Bitwise NOT of a is : -2

Bitwsie XOR

This operator is the same as the XOR gate that we studied in the digital electronics chapter, as shown below:

The Bitwise XOR operator is denoted by ^. When an XOR gate is given with 2 inputs, the corresponding outputs will be:

• If two input bits are different, the output is 1.
• In all other cases, it is 0.

1^1 => yields to 0
0^0 => yields to 0
1^0 => yields to 1
0^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 0110
---------------------------------

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

Bitwise Left, Right

A bit shift is a Bitwise operation where the order of a series of bits is moved, either to the left or right, to efficiently perform a mathematical operation.

A bit shift moves each digit in a number’s binary representation left or right. The bit-shifting operators do precisely what their name implies: they shift bits. Here is a brief introduction to the different shift operators.

Types

There are three main types of shifts:

1. Left shift: << is the left shift operator and meets both logical and arithmetic shifts’ needs.
2. Arithmetic/signed right shift: >> is the arithmetic (or signed) right shift operator.
3. Logical/unsigned right shift: >>> is the logical (or unsigned) right shift operator. > Note: <<< is not an operator because it would be redundant. These operators can be applied to integer values int, long, short, byte or char.

In some languages, applying the shift operators to any datatype smaller than int automatically resizes the operand to be an int.

Left shift

The left shift operator is written as <<.

Integers are stored in memory as a series of bits. For example, the number 6 stored as a 32-bit int would be:

6 = 00000000 00000000 00000000 00000110

Shifting this bit pattern to the left one position (6 << 1) would result 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. You might also note that shifting left is equivalent to multiplication by powers of 2.

So,

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

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

A good optimization compiler will replace multiplications with shifts when possible.

32-bit representation

00000000 00000000 00000000 00000010 << 1  →  00000000 00000000 00000000 00000100

4-bit representation

0010 << 2  →  1000

As seen above, a single left shift multiplies a binary number by 2.

0010 << 1  →  0100

0010 is 2
0100 is 4

Formula

a << b = (a * 2^b)

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

Logical right shifts

The logical right-shift operator is written as >>>.

Integers are stored in memory as a series of bits. For example, the number 12 stored as a 32-bit int would be:

12 = 00000000 00000000 00000000 00001100

When we shift it one position (12 >>> 1), the answer is 6.

12 >>> 1 = 12/2^1 = 12/2 = 6

The binary representation of the number 6 is as follows.

(12 >>> 1) = 00000000 00000000 00000000 00000110

Formula

a >>> b = a/2^b

Arithmetic right shift (>>)

Right shift

The right shift operator is written as >>.

Integers are stored in memory as a series of bits. For example, the number 6 stored as a 32-bit int would be:

6 = 00000000 00000000 00000000 00000110

Shifting this bit pattern to the right one position (6 >> 1) would result in the number 3:

6 >> 1 = 00000000 00000000 00000000 00000011

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

So,

6 >> 1 => 6/2^1 = 6/2 = 3

6 >> 3 => 6/2^3 = 6/8 = 0

A good optimization compiler will replace division with shifts when possible.

1011 >> 1  →  1101
1011 >> 3  →  1111

0011 >> 1  →  0001
0011 >> 2  →  0000

The first two numbers had a 1 as the most significant bit, so more 1's were inserted during the shift. The last two numbers had a 0 as the most significant bit, so the shift inserted more 0's.

If a number is encoded using two’s complement, then an arithmetic right shift preserves the number’s sign, while a logical right shift makes the number positive.

// Arithmetic shift
1011 >> 1  →  1101    
    1011 is -5    
    1101 is -3

Formula

x >> y = x/2^y

class RightShift {
   private static int helper(int number, int i) {
        return number >> i;// divides `number` with 2^i times.
    }

    public static void main(String[] args) {
        int number = 100;

        System.out.println(number + " shifted 1 position right, yields to " + helper(number, 1));
        System.out.println(number + " shifted 2 positions right, yields to " + helper(number, 2));
        System.out.println(number + " shifted 3 positions right, yields to " + helper(number, 3));
        System.out.println(number + " shifted 4 positions right, yields to " + helper(number, 4));
    }
}

This concludes the basics of the bitwise operators. Please feel free to check my course on https://www.educative.io/courses/bit-manipulation. You can get up to 40% discount using https://www.educative.io/gopi. Or you can always visit the same course on my website for free.