### Bit Manipulation - The Coding Shala

Home >> Algorithms >> Bit Manipulation

In this post, we will learn the basics of Bit Manipulation.

## Bit Manipulation

As we know Bit stands for binary digits, the smallest unit of data in the computer. The bit can be either 0 or 1.

**What is Bit Manipulation?**

Bit manipulation is the process of using bitwise operations on the sequence of bits to get a required result.

First, we will see bitwise operators that we use.

#### & ( and operator)

If both the bits are 1 then the answer will be 1.

0 & 0 = 0

0 & 1 = 0

1 & 0 = 0

1 & 1 = 1

let's take an example

A = 5

B = 3

A & B = 5 & 3 = 101 & 011 = 001 = 1

#### | (or operator)

Return 1 if any bit is 1.

0 | 0 = 0

0 | 1 = 1

1 | 0 = 1

1 | 1 = 1

#### ^ (xor operator)

Return 1 if both the bits are different else 0.

0 ^ 0 = 0

0 ^ 1 = 1

1 ^ 0 = 1

1 ^ 1 = 1

#### ~ (not operator)

Use to flip the bits.

~0 = 1

~1 = 0

#### >> ( right shift)

Shifts all the bits to right position. (divies by two).

For example:

A = 29 ( 11101)

A >> 2 = 1 1 1 0 1 >> 2 = 0 0 1 1 1 = 7

Note: In the right shift most significant bit(left-most bit) will be replaced by 0.

#### << (left shift)

Shifts the bits to the left position. (multiplies by two).

For Example:

A = 29 ( 11101), or ( 0011101)

A << 2 = 0 0 1 1 1 0 1 << 2 = 1 1 1 0 1 0 0 = 116

Note: In the left shift, the least bit(rightmost bit) will be replaced by 0.

Remember: Logical Operators will return different results than bitwise operations.

**What is the difference between Logical Shift(>>) and Arithmetic Shift(>>>)?**

The logical shift right inserts a 0 in the sing bit while the Arithmetic shift keeps the sign bit.

Example:

1 0 1 1 0 1 0 1 (-75) >> 1 = 0 1 0 1 1 0 1 0 (90)

1 0 1 1 0 1 0 1 (-75) >>> 1 = 1 1 0 1 1 0 1 0 (-38)

#### 1's Complement

1's complement of a binary number is obtained by inverting(toggling) all the bits in it.

Example:

1's complement of 0101 is 1010.

#### 2's Complement

If we add 1 to the 1's complement of the binary number then we get two's complement of a binary number.

For example:

A = 0111

step 1: intver all bits(one's complement)

A = 1000

step 2: add 1

A = 1000 + 1 = 1001

**Why Two's Complement used?**

Negative numbers are usually stored in computers in the form of two's complement. For the positive number, we use 0 in the sign bit(leftmost) with its binary number while a negative number is represented as the two's complement with 1 in the sign bit.

Example:

7 = 0 111

-7 = 1 001

**Other Posts You May Like**- The Big O Notation
- Binary Search Algorithm
- Merge Sort Algorithm
- Selection Sort Algorithm
- Sliding Window Algorithm

## Comments

## Post a Comment