Introduction
This article serves as an introduction to some fundamental concepts in binary number manipulation, including binary number conversion, one's complement, and two's complement and many more concepts. These concepts are not only fundamental to understanding how computers work but also crucial for solving a variety of problems in computer science.
Having an understanding of binary numbers is extremely important in the field of computer science as everything stored in a computer is in the form of only 0s and 1s.
Binary Number Conversion
Decimal to Binary Conversion:
By repeatedly dividing a number by 2 and recording the result, decimal values can be transformed into binary
Example:
Converting 13 to its binary equivalent
- Start with the decimal number 13.
- Divide the number by 2 and record the remainder.
- Repeat the division with the quotient until the number becomes 0.
13 / 2 = 6 remainder 1
6 / 2 = 3 remainder 0
3 / 2 = 1 remainder 1
1 / 2 = 0 remainder 1
To obtain the binary equivalent of 13, the remainders must be read from bottom to top, i.e., 1101.
So, the binary equivalent of 13 is 1101.
Pseudo Code:
12345678910111213
string decimalToBinary(int n) {
result = ""
while(n != 1) {
if(n % 2 == 1) result += '1'
else result += '0'
n = n / 2
}
reverse(result)
return result
}
Complexity Analysis:
Time Complexity: O(logN) Since the number is divided by 2 continuously.
Space Complexity: O(logN) Storing the bits.
Binary to Decimal Conversion:
Converting a binary number back to its decimal equivalent involves a reverse process.
Example:
Converting 1101 to its decimal equivalent
- Start from the rightmost bit (least significant bit) and move to the left.
- Each bit is multiplied by 2 raised to the power of its position index (starting from 0).
1 * 2^0 = 1
0 * 2^1 = 0
1 * 2^2 = 4
1 * 2^3 = 8
Summing these values will give the number, i.e., 1 + 0 + 4 + 8 = 13.
Hence, the decimal equivalent of the binary number 1101 is 13.
Pseudo Code:
1234567891011121314
string binaryToDecimal(string str) {
len = str.length
val = 1, num = 0
for(i from len-1 to 0) {
if(str[i] == '1') {
num = num + val
}
val = val * 2
}
return num
}
Complexity Analysis:
Time Complexity: O(n) Traversing every bit in the string.
Space Complexity: O(1) Couple of variables used.
Understanding One's Complement and Two's Complement
One's Complement
The one's complement of a binary number is obtained by flipping all the bits. For example, the one's complement of 13 (binary 1101) is:
0000 1101 (binary of 13)
1111 0010 (one's complement of 13)
Two's Complement
The two's complement is obtained by taking the one's complement of a number and then adding 1. For example, the two's complement of 13 (binary 1101) is:
- Find the one's complement:
0000 1101 (binary of 13)
1111 0010 (one's complement of 13)
- Add 1 to the one's complement:
1111 0011
Bitwise Operators
AND Operator
The AND operator is denoted by & and performs a bitwise AND operation. If both corresponding bits are 1, the resulting bit is 1; otherwise, the resulting bit is 0.
Example: 13 & 7 is:
13: 1101
7: 0111
& -------
5: 0101
OR Operator
The OR operator is denoted by | and performs a bitwise OR operation. If either corresponding bit is 1, the resulting bit is 1; otherwise, the resulting bit is 0.
Example: 13 | 7 is:
13: 1101
7: 0111
| --------
15: 1111
XOR Operator
The XOR operator is denoted by ^ and performs a bitwise XOR operation. If the number of 1s in corresponding bit positions is odd, the resulting bit is 1; if even, the resulting bit is 0.
Example: 13 ^ 7 is:
13: 1101
7: 0111
^ --------
10: 1010
NOT Operator
The NOT operator is denoted by ~ and flips all the bits in the number.
Example: ~5 is:
5: 0000 0101
~5: 1111 1010 (which is -6 in two's complement)
Shift Operators
-
Right Shift (>>): Shifts the bits to the right, discarding the bits that fall off and filling the leftmost bits with zeros.
Example:
13 >> 1 = 1101 >> 1 = 0110 (binary of 6)
-
Left Shift (<<): Shifts the bits to the left, discarding the bits that fall off and filling the rightmost bits with zeros.
Example:
13 << 1 = 1101 << 1 = 11010 (binary of 26)
Bit Manipulation Tricks and Techniques
1. Swapping Two Numbers Without a Third Variable
Swapping two numbers can be efficiently done using the XOR operator, without the need for a temporary variable.
Example:
Given two numbers A = 5 and B = 6, swap them using XOR.
- Step 1: A = A ^ B; (A becomes 3)
- Step 2: B = A ^ B; (B becomes 5)
- Step 3: A = A ^ B; (A becomes 6)
The numbers are swapped: A = 6, B = 5.
Pseudo Code:
1234
// To swap two numbers A and B using XOR operations
A = A ^ B
B = A ^ B
A = A ^ B
Complexity Analysis:
Time Complexity: O(1) Each XOR operation is constant time.
Space Complexity: O(1) No extra space used.
2. Checking if the i-th Bit is Set
To check if the i-th bit of a number is set, either the left shift or the right shift operator can be used.
Example:
Given a number 13 (binary 1101) and i = 2, check if the 2nd bit is set.
- Left Shift: (1 << 2) results in 100. Perform AND with 13: 1101 & 0100 = 0100 (non-zero, hence the bit is set).
- Right Shift: (13 >> 2) results in 0011. Perform AND with 1: 0011 & 0001 = 0001 (non-zero, hence the bit is set).
Pseudo Code:
1234
// Function to determine if the ith bit is set in N
bool isBitSet(int n, int i) {
return (n & (1 << i)) != 0;
}
Complexity Analysis:
Time Complexity: O(1) Each operation is constant time.
Space Complexity: O(1) No extra space used.
3. Setting the i-th Bit
To set the i-th bit of a number to 1, the bitwise OR operator can be used.
Example:
Given a number 9 (binary 1001) and i = 2, set the 2nd bit.
Step: (9 | (1 << 2)) results in 1101, which is 13.
Pseudo Code:
1234
// Function to set the ith bit in N
int setBit(int n, int i) {
return n | (1 << i);
}
Complexity Analysis:
Time Complexity: O(1) Each operation is constant time.
Space Complexity: O(1) No extra space used.
4. Clearing the i-th Bit
To clear the i-th bit of a number, the bitwise AND operator can be used with the complement of the bit mask.
Example:
Given a number 13 (binary 1101) and i = 2, clear the 2nd bit.
Step: (13 & ~(1 << 2)) results in 1001, which is 9.
Pseudo Code:
1234
// Function to clear the ith bit in N
int clearBit(int n, int i) {
return n & ~(1 << i);
}
Complexity Analysis:
Time Complexity: O(1) Each operation is constant time.
Space Complexity: O(1) No extra space used.
5. Toggling the i-th Bit
Given a number 13 (binary 1101) and i = 1, toggle the 1st bit.
Example:
Given a number 13 (binary 1101) and i = 2, clear the 2nd bit.
Step:(13 ^ (1 << 1)) results in 1111, which is 15.
Pseudo Code:
1234
// Function to toggle the ith bit in N
int toggleBit(int n, int i) {
return n ^ (1 << i);
}
Complexity Analysis:
Time Complexity: O(1) Each operation is constant time.
Space Complexity: O(1) No extra space used.
6. Removing the Last Set Bit
To remove the last set bit (rightmost set bit) of a number, the bitwise AND operator with n-1 can be used.
Example:
Given a number 13 (binary 1101), remove the last set bit.
Step:(13 & (13 - 1)) results in 1100, which is 12.
Pseudo Code:
1234
// Function to remove the last set bit
int removeLastSetBit(int n) {
return n & (n - 1);
}
Complexity Analysis:
Time Complexity: O(1) Each operation is constant time.
Space Complexity: O(1) No extra space used.
7. Checking if a Number is a Power of 2
To check if a number is a power of 2, the bitwise AND operator with n-1 can be used. If the result is 0, the number is a power of 2.
Example:
Given a number 16, check if it is a power of 2.
Step:(16 & (16 - 1)) results in 0, hence 16 is a power of 2.
Pseudo Code:
1234
// Function to determine if the number is a power of 2
bool isPowerOfTwo(int n) {
return (n > 0) && ((n & (n - 1)) == 0);
}
Complexity Analysis:
Time Complexity: O(1) Each operation is constant time.
Space Complexity: O(1) No extra space used.
8. Counting the Number of Set Bits
Using a Loop and Bitwise AND
To count the number of set bits (1s) in a binary representation of a number, a loop can be used along with the bitwise AND operator.
Example:
Given a number 13 (binary 1101), count the set bits.
- Step: (13 & 1) results in 1 (increment count)
- Right shift 13 to get 110, (6 & 1) results in 0
- Right shift 6 to get 11, (3 & 1) results in 1 (increment count)
- Right shift 3 to get 1, (1 & 1) results in 1 (increment count)
The number 13 has 3 set bits.
Pseudo Code:
123456789
// Function to determine the number of set bits
int countSetBits(int n) {
int count = 0;
while (n > 0) {
count += (n & 1);
n >>= 1;
}
return count;
}
Complexity Analysis:
Time Complexity: O(logN) Each bit is checked once.
Space Complexity: O(1) No extra space used.
Optimized Approach Using n & (n-1)
An optimized approach to count set bits involves repeatedly turning off the rightmost set bit using n & (n-1).
Example:
Given a number 13 (binary 1101), keep on turning the rightmost set bit.
- Keep on unsetting the last set bit in the number until the number has no set bits left.
- The number of times the last bit is unset, will determine the number of set bits.
The number 13 has 3 set bits.
Pseudo Code:
123456789
// Function to determine the number of set bits
int countSetBits(int n) {
int count = 0;
while (n) {
n &= (n - 1);
count++;
}
return count;
}
Complexity Analysis:
Time Complexity: O(K) Where K is the number of set bits.
Space Complexity: O(1) No extra space used.