## DEV Community

Gopi Gorantala

Posted on • Updated on

# A Guide To Master Bit Manipulation For Coding Interviews

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

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.

Number System Base Used Digits
Binary 2 0, 1
Octal 8 0, 1, 2, 3, 4, 5, 6, 7
Decimal 10 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Hexadecimal 16 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

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

Power of two Binary Decimal Value
2^0 0001 1
2^1 0010 2
2^2 0100 4
2^3 1000 8
2^4 0001 0000 16
2^5 0010 0000 32
2^6 0100 0000 64
2^7 1000 0000 128
2^8 0001 0000 0000 256
2^9 0010 0000 0000 512
2^10 0100 0000 0000 1,024

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 20, the next representing 21, then 22, 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:

1001012 = [ ( 1 ) x 25 ] + [ ( 0 ) x 24 ] + [ ( 0 ) x 23 ] + [ ( 1 ) x 22 ] + [ ( 0 ) x 21 ] + [ ( 1 ) x 20 ]

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

1001012 = 3710

## 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 b a | b
0 0 0
0 1 1
1 0 1
1 1 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:

a ~a
1 0
0 1

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 b a ^ b
0 0 0
0 1 1
1 0 1
1 1 0
``````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.