A Guide To Master Bit Manipulation For Coding Interviews
Tags: java, python, javascript, cpp
Published: 2023-10-15 13:58:27

<mark>You can find the complete Bit manipulation tutorial on my website for FREE.</mark>

🚀 [https://www.ggorantala.dev/courses/](https://www.ggorantala.dev/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.

<table>
    <tr>
        <th style="text-align:center">Number System</th>
        <th style="text-align:center">Base</th>
        <th style="text-align:center">Used Digits</th>
    </tr>
    <tr>
        <td style="text-align:center">Binary</td>
        <td style="text-align:center">2</td>
        <td style="text-align:center">0, 1</td>
    </tr>
    <tr>
        <td style="text-align:center">Octal</td>
        <td style="text-align:center">8</td>
        <td style="text-align:center">0, 1, 2, 3, 4, 5, 6, 7</td>
    </tr>
    <tr>
        <td style="text-align:center">Decimal</td>
        <td style="text-align:center">10</td>
        <td style="text-align:center">0, 1, 2, 3, 4, 5, 6, 7, 8, 9</td>
    </tr>
    <tr>
        <td style="text-align:center">Hexadecimal</td>
        <td style="text-align:center">16</td>
        <td style="text-align:center">0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F</td>
    </tr>
</table>

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

<table>
    <tr>
        <th style="text-align:center">Power of two</th>
        <th style="text-align:center">Binary</th>
        <th style="text-align:center">Decimal Value</th>
    </tr>
    <tr>
        <td style="text-align:center">2^0</td>
        <td style="text-align:center">0001</td>
        <td style="text-align:center">1</td>
    </tr>
    <tr>
        <td style="text-align:center">2^1</td>
        <td style="text-align:center">0010</td>
        <td style="text-align:center">2</td>
    </tr>
    <tr>
        <td style="text-align:center">2^2</td>
        <td style="text-align:center">0100</td>
        <td style="text-align:center">4</td>
    </tr>
    <tr>
        <td style="text-align:center">2^3</td>
        <td style="text-align:center">1000</td>
        <td style="text-align:center">8</td>
    </tr>
    <tr>
        <td style="text-align:center">2^4</td>
        <td style="text-align:center">0001 0000</td>
        <td style="text-align:center">16</td>
    </tr>
    <tr>
        <td style="text-align:center">2^5</td>
        <td style="text-align:center">0010 0000</td>
        <td style="text-align:center">32</td>
    </tr>
    <tr>
        <td style="text-align:center">2^6</td>
        <td style="text-align:center">0100 0000</td>
        <td style="text-align:center">64</td>
    </tr>
    <tr>
        <td style="text-align:center">2^7</td>
        <td style="text-align:center">1000 0000</td>
        <td style="text-align:center">128</td>
    </tr>
    <tr>
        <td style="text-align:center">2^8</td>
        <td style="text-align:center">0001 0000 0000</td>
        <td style="text-align:center">256</td>
    </tr>
    <tr>
        <td style="text-align:center">2^9</td>
        <td style="text-align:center">0010 0000 0000</td>
        <td style="text-align:center">512</td>
    </tr>
    <tr>
        <td style="text-align:center">2^10</td>
        <td style="text-align:center">0100 0000 0000</td>
        <td style="text-align:center">1,024</td>
    </tr>
</table>

**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<sup>0</sup>, the next representing 2<sup>1</sup>, then 2<sup>2</sup>, 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<sub>2</sub> = [ ( 1 ) x 2<sup>5</sup> ] + [ ( 0 ) x 2<sup>4</sup> ] + [ ( 0 ) x 2<sup>3</sup> ] + [ ( 1 ) x 2<sup>2</sup> ] + [ ( 0 ) x 2<sup>1</sup> ] + [ ( 1 ) x 2<sup>0</sup> ]

100101<sub>2</sub> = [ ( 1 ) x 32 ] + [ ( 0 ) x 16 ] + [ ( 0 ) x 8 ] + [ ( 1 ) x 4 ] + [ ( 0 ) x 2 ] + [ ( 1 ) x 0 ]

100101<sub>2</sub> = 37<sub>10</sub>

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

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

### 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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8lm9f2pzeal5q9zop9s9.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2f472xn0lywfpg1ohcbk.png)

Let us visualize the steps in detail:

![AND Operator](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nnx87xsm57maef08bt2a.png)

```java
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:

![OR Operator Image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0nax2bu1d7cjq6oxqhqa.png)

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

<table>
    <tr>
        <th style="text-align:center">    a</th>
        <th style="text-align:center">    b</th>
        <th style="text-align:center">a | b</th>
    </tr>
    <tr>
        <td style="text-align:center">0</td>
        <td style="text-align:center">0</td>
        <td style="text-align:center">0</td>
    </tr>
    <tr>
        <td style="text-align:center">0</td>
        <td style="text-align:center">1</td>
        <td style="text-align:center">1</td>
    </tr>
    <tr>
        <td style="text-align:center">1</td>
        <td style="text-align:center">0</td>
        <td style="text-align:center">1</td>
    </tr>
    <tr>
        <td style="text-align:center">1</td>
        <td style="text-align:center">1</td>
        <td style="text-align:center">1</td>
    </tr>
</table>

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

```java
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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vyk8dea7whutiszb6poi.png)

<table>
    <tr>
        <th style="text-align:center">a</th>
        <th style="text-align:center">~a</th>
    </tr>
    <tr>
        <td style="text-align:center">1</td>
        <td style="text-align:center">0</td>
    </tr>
    <tr>
        <td style="text-align:center">0</td>
        <td style="text-align:center">1</td>
    </tr>
</table>

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:

```java
x  = 00000000 00000000 00000000 00000001
```
Now, Bitwise NOT of `x` will be:

```java
~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)

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

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

So,  a = 1 becomes -2(~a)
```
<mark>I can't give many details about 2's compliment here as this article size will last longer. The course explains everything.</mark>

```java
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:


![XOR Gate](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/02s3mc2x016my13cfveq.png)

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

<table>
    <tr>
        <th style="text-align:center">    a</th>
        <th style="text-align:center">    b</th>
        <th style="text-align:center">a ^ b</th>
    </tr>
    <tr>
        <td style="text-align:center">0</td>
        <td style="text-align:center">0</td>
        <td style="text-align:center">0</td>
    </tr>
    <tr>
        <td style="text-align:center">0</td>
        <td style="text-align:center">1</td>
        <td style="text-align:center">1</td>
    </tr>
    <tr>
        <td style="text-align:center">1</td>
        <td style="text-align:center">0</td>
        <td style="text-align:center">1</td>
    </tr>
    <tr>
        <td style="text-align:center">1</td>
        <td style="text-align:center">1</td>
        <td style="text-align:center">0</td>
    </tr>
</table>

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

```java
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:
```java
6 = 00000000 00000000 00000000 00000110
```

Shifting this bit pattern to the left one position `(6 << 1)` would result in the number `12`:
```java
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,
```java
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.

```java
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.
```java
0010 << 1  →  0100

0010 is 2
0100 is 4
```

### Formula
```java
a << b = (a * 2^b)
```
```java
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:
```java
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.

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

### Formula
```java
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:

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

```java
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.
```java
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.
```java
// Arithmetic shift
1011 >> 1  →  1101    
	1011 is -5    
	1101 is -3
```

### Formula
```java
x >> y = x/2^y
```

```java
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](https://www.educative.io/courses/bit-manipulation?aff=xjzd). You can get up to 40% discount using [https://www.educative.io/gopi](https://www.educative.io/gopi). Or you can always visit the same course on my website for free.