Bit Manipulation is one of the most powerful and efficient techniques in programming. It involves working directly with binary digits (0s and 1s) using special operators called bitwise operators.
You may not realize it, but every number in your computer is stored in binary, and by manipulating these bits smartly, you can solve many problems faster and with less memory.
In this article, we’ll break down what bits are, how to convert between decimal and binary, and how to use bitwise operators with simple examples. We’ll also explain the concept of 2’s complement, which is used to represent negative numbers in binary.
What is a Bit?
A bit (short for binary digit) is the smallest unit of data in a computer. It can have only two possible values:
- 0 (OFF)
- 1 (ON)
All information in a computer — numbers, characters, images — is stored using bits. Multiple bits are grouped together to represent more complex data. For example:
- 1 Byte = 8 bits
- 5 in binary (8-bit) = 00000101
What is Bit Manipulation?
Bit Manipulation is a programming technique that involves working directly with the individual bits (0s and 1s) of a number using special operators called bitwise operators.
In simple terms, it's a way to perform fast and efficient operations by changing or checking the binary form of numbers — the language that computers understand best.
Bit manipulation helps in:
- Optimizing performance
- Saving memory using bit flags or masks
- Solving mathematical and logical problems more efficiently
It’s widely used in competitive programming, system-level code, and interview problem-solving.
Before diving into bit manipulation techniques, it’s important to understand how numbers are represented in binary form. Since bit manipulation deals with binary digits (bits) directly, knowing how to convert between decimal and binary is the foundation.
Decimal to Binary Conversion.
To convert a decimal number to binary, we use repeated division by 2.
Steps:
- Divide the number by 2.
- Record the remainder (it will be 0 or 1).
- Continue dividing the quotient by 2 until it becomes 0.
- The binary number is the reverse order of the remainders.
Example: Convert 13 to Binary
13 ÷ 2 = 6 remainder 1
6 ÷ 2 = 3 remainder 0
3 ÷ 2 = 1 remainder 1
1 ÷ 2 = 0 remainder 1
→ Binary = 1101Binary to Decimal Conversion
To convert a binary number to decimal, we multiply each bit by 2 raised to the power of its position (starting from the right, index 0).
Steps:
- Start from the rightmost bit.
- Multiply each bit by 2^position.
- Sum all the results.
Example: Convert 1010 to Decimal
= 1×2³ + 0×2² + 1×2¹ + 0×2⁰
= 8 + 0 + 2 + 0
= 10
Now that you know how to convert a decimal number to binary and how to represent numbers in binary form, it's the right time to understand Bitwise Operators.
Bitwise Operators.
Bitwise operators allow us to directly manipulate individual bits of binary numbers. These operators form the backbone of bit manipulation techniques used in coding problems and optimization.
Let’s explore each bitwise operator with simple examples.
1. Bitwise AND (&)- The AND operator compares two bits and returns 1 only if both bits are 1; otherwise, it returns 0.
Truth Table of Bitwise AND
| A | B | A & B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Example:
5 = 0101
3 = 0011
5 & 3 = 0001 → 1
2. Bitwise OR (|)- The OR operator returns 1 if at least one of the bits is 1.
Truth Table of Bitwise OR
| A | B | A | B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Example:
3. Bitwise XOR (^)- The XOR (exclusive OR) operator returns 1 only if the two bits are different.
5 = 0101
3 = 0011
5 | 3 = 0111 → 7
Truth Table of Bitwise XOR
| A | B | A ^ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Example:
5 = 0101
3 = 0011
5 ^ 3 = 0110 → 6
4. Bitwise NOT (~)- The NOT operator flips each bit:
- 0 becomes 1
- 1 becomes 0
However, in most programming languages (like C++, Java, Python), numbers are stored in 2’s complement format, so applying ~ to a number results in -(n + 1). At the end of this article, we have explained 2's Complement in detail.
Example:
~5 = -(5 + 1) = -6
Let's break it down:
5 = 00000101
~5 = 11111010 (in 8-bit) → which is -6 in 2’s complement
5. Left Shift (<<)- The left shift operator shifts bits to the left by a given number of positions. Each left shift is equivalent to multiplying the number by 2^n.
Example:
5 << 1 = 10
Binary: 0101 << 1 → 1010
6. Right Shift (>>)- The right shift operator shifts bits to the right. Each right shift divides the number by 2^n, ignoring the remainder.
Example:
5 >> 1 = 2
Binary: 0101 >> 1 → 0010
That's all about the Bitwise Operators that we will use to solve problems using bit manipulation.
Let's understand one last topic of in introduction part, and that is 2's Complement. Many times, learners find it difficult to understand this and their use.
What is 2's Complement?
2’s Complement is a method used by computers to represent negative numbers in binary form. It allows addition, subtraction, and other operations to work seamlessly with both positive and negative integers using the same circuitry.
How to Find 2’s Complement?
To find the 2’s complement of a positive number:
- Write the number in binary (fixed width, e.g., 8 bits).
- Invert all the bits (change 0 to 1 and 1 to 0).
- Add 1 to the result.
With 2’s complement:
- Positive numbers start from 00000000 (0) to 01111111 (+127)
- Negative numbers start from 11111111 (–1) to 10000000 (–128)
Example: Find the 2’s Complement of 5
Step 1: Binary of 5 in 8 bits = 00000101
Step 2: Invert bits → 11111010
Step 3: Add 1 → 11111011
Result: 11111011 is -5 in 2’s complement form.
Bit manipulation is a powerful concept that allows you to write faster and more memory-efficient programs. By mastering binary conversions and bitwise operators, you unlock the ability to solve a wide range of DSA problems more effectively.
No comments:
Post a Comment