Binary Numbers
A binary number is a number that is represented by using two digits only, usually 0 and 1.
In C++, there are either 32-bit or 64-bit numbers an are stored as
Significant bits
MSB
- Most Significant Bit(high-order bit or left-most bit)
- The MSB gives the sign of the number (sign bit) , 0 for positive and 1 for negative.
LSB
- Least Significant Bit(low-order bit or right-most bit)
- To determine whether the number is even or odd.
Signed and Unsigned 32-bit Int
Unsigned Integer
These uses all the 32 bits to store the magnitude of the number. As a result there is no way to determine whether polarity of the number so we assume the number to be +ve.The range of unsigned binary number is from 0 to (2n-1).
Minimum Possible Value
When all the bits are set to 0.
$\rightarrow (2^{31} \cdot 0) + (2^{30} \cdot 0) + \ldots( 2^0 \cdot 0) = 0$
1
unsigned int mini = 0;
Maximum Possible Value
When all the bits are set to 1.
$\rightarrow (2^{31} \cdot 1) + (2^{30} \cdot 1) + \ldots + (2^0 \cdot 1) $
$\rightarrow 2^{32} - 1 = 4,294,967,295 $ (approx. 4 billion)
1
unsigned int maxi = UINT_MAX;
Signed
The first bit from the left(msb) is reserved. All the positive integers are stored as it is. For negative numbers, we set the msb to 1 and then store the rest of the number in 2’s complement. Why ?
- To avoid double representation of 0.
- Also increases the range by one.
2’s Complement
2’s complement of a number is obtained by inverting each bit of given number plus 1 to least significant bit(LSB).
Note: Overflow is ignored while computing 2’s complement.
Minimum Possible Value
When all the bits are set to 1.
$\rightarrow - {(2^{31} \cdot 1) + (2^{30} \cdot 1) + \ldots + (2^0 \cdot 1)} $
$\rightarrow -2^{31} = –2,147,483,648 $ (approx. -2 billion)
1
int mini = INT_MIN;
Maximum Possible Value
When all the bits are set to 1, except the MSB.
$\rightarrow (2^{31} \cdot 1) + (2^{30} \cdot 1) + \ldots + (2^0 \cdot 1) $
$\rightarrow 2^{31} - 1 = 2,147,483,647 $ (approx. 2 billion)
1
int maxi = INT_MAX;
Bitwise Operators
Types of operators
| Operator | Operation |
|---|---|
| & | AND |
| | | OR |
| ^ | XOR |
| » | Left Shift |
| « | Right Shift |
| ~ | NOT |
Unary operators
& - Bitwise AND
Performs bitwise AND on every bit of the operands.
1
2
int a = 7, b = 9;
cout << 7 & 9 << endl;
| 0 & 0 | 0 |
| 1 & 0 | 0 |
| 1 & 1 | 1 |
| - Bitwise OR
Performs bitwise OR on every bit of the operands.
1
2
int a = 7, b = 9;
cout << 7 | 9 << endl;
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
^ - Bitwise XOR
Performs bitwise XOR on every bit of the operands.
1
2
int a = 7, b = 9;
cout << 7 ^ 9 << endl;
| 0 ^ 0 | 0 |
| 1 ^ 0 | 1 |
| 1 ^ 1 | 0 |
- x ^ 0 = x
- x ^ x = 0
- x ^ y = y ^ x
~ - Bitwise NOT
Inverts all bits of the operand.
1
2
int a = 7
cout << (~7) << endl;
| ~0 | 1 |
| ~1 | 0 |
~a$\implies$INT_MAX - a(only for +ve integers)
RSB
Subtracting 1 from a decimal number flips all the bits after the rightmost set bit including the rightmost set bit.
1
2
3
110100 (52)
110100 - 0000001 (52 - 1)
110011 (51)
To find the right most set bit of a number we can perform AND between the given number and inverse of the number decremented by 1.
1
int rsb = a & ~(a-1);
1
2
3
4
5
6
7
8
110100 (52)
110011 (51)
001100 ~(51)
110100 (52)
& 001100 ~(51)
000100 (Right most set bit)
Binary operators
« (Left Shift)
1
2
int a = 7, b = 2;
cout << (b << a) << endl;
1
2
00000111 << 2 (7 << 2)
00001100 (28)
The above operation will shift all bits of ‘b’, ‘a’ bits towards the left. Bits vacated after shifting are filled with 0.
- b « a $\implies b \times 2^a $
» (Right Shift)
1
2
int a = 7, b = 2;
cout << (b >> a) << endl;
1
2
00000111 >> 2 (7 >> 2)
00000001 (1)
The above operation will shift all bits of ‘b’, ‘a’ bits towards the right. Bits vacated after shifting are filled with 0.
- b » a $\implies \lfloor \frac{b}{2^a} \rfloor $
Problems
Check Kth bit is set or not
Given a number n, check if the Kth bit of n is set or not.
Using left shift
1
2
3
4
5
bool kthbit(int k, int n){
if (n & (1 << (k - 1)))
return true;
return false;
}
Time Complexity: $O(1)$
Using right shift
1
2
3
4
5
bool kthbit(int k, int n){
if ((n >> (k-1)&1))
return true;
return false;
}
Time Complexity: $O(1)$
Count set bit
Write a program to count the number of 1s in the binary representation of an integer.
Naive
1
2
3
4
5
6
7
8
9
int setBits(int N) {
int count = 0;
while(N){
count += (N & 1);
N = N >> 1;
}
return count;
}
Time Complexity: $O(logn)$
Brian Kernighan’s Algorithm
1
2
3
4
5
6
7
8
int setBits(int N) {
int count = 0;
while (N) {
N &= (N - 1);
count++;
}
return count;
}
Time Complexity: $O(logn)$
Using Lookup Table
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int bits[256];
void initialize()
{
bits[0] = 0;
for (int i = 0; i < 256; i++)
{
bits[i] = (i & 1) + bits[i / 2];
}
}
int setBits(int n)
{
return (bits[n & 0xff] + bits[(n >> 8) & 0xff] + bits[(n >> 16) & 0xff] + bits[n >> 24]);
}
Time Complexity: $O(1)$
Detect if two integers have opposite signs
Given two signed integers, write a function that returns true if the signs of given integers are different, otherwise false.
Arithmetic comparison
1
2
3
4
bool oppositeSigns(int x, int y)
{
return (x < 0) ? (y >= 0) : (y < 0);
}
Using XOR
We can utilize the fact that XOR operation evalutes to 1 iff both the operands differ from each other. So we can say that the resultant MSB would be 1 iff x and y have opposite signs.
1
2
3
4
bool oppositeSigns(int x, int y)
{
return ((x ^ y) < 0);
}
Swap two numbers without using temp variable
Given two variables, x, and y, swap two variables without using a third variable.
Arithmetic Operators
1
2
3
4
5
6
void swapped(int* x, int* y)
{
x = x + y;
y = x - y;
x = x - y;
}
Using XOR
Use the fact x ^ x = 0
1
2
3
4
5
6
void swapped(int* x, int* y)
{
x = x ^ y;
y = x ^ y;
x = x ^ y;
}
Is power of 2
Given a positive integer, write a function to find if it is a power of two or not.
Naive
1
2
3
4
5
6
7
8
9
10
11
12
int setBits(int N) {
if (n == 0)
return 0;
while (n != 1)
{
if (n%2 != 0)
return 0;
n = n/2;
}
return 1;
}
Time Complexity: $O(logn)$
Brian Kernighan’s Algorithm
1
2
3
4
5
6
7
8
9
10
11
int setBits(int N) {
if(!N) return false;
int count = 0;
while (N) {
N &= (N - 1);
count++;
}
return count == 1;
}
Time Complexity: $O(logn)$
Optimized
1
2
3
bool isPowerofTwo(long long n){
return n && (!(n&(n-1)));
}
Time Complexity: $O(1)$
Using log
1
2
3
bool isPowerofTwo(long long n){
if(!n) return false;
return (ceil(log2(n)) == floor(log2(n)));
Time Complexity: $O(1)$
Add two numbers without using arithmetic operators
Write a function that returns sum of two integers. The function should not use any of the arithmetic operators
1
2
3
4
5
6
7
8
9
10
int Add(int x, int y)
{
while (y)
{
unsigned carry = x & y;
x = x ^ y;
y = carry << 1;
}
return x;
}
Find odd occuring number
Given an array of positive integers. All numbers occur an even number of times except one number which occurs an odd number of times.
Naive
Use hashmap to store the frequency.
Time Complexity: $O(n)$
Auxiliary Space: $O(n)$
Using XOR
use the fact that a ^ a = 0
1
2
3
4
5
6
7
int oddoccur(int arr[], int arr_size)
{
int res = 0;
for (int i = 0; i < arr_size; i++)
res = res ^ arr[i];
return res;
}
Time Complexity: $O(n)$
Auxiliary Space: $O(1)$
Find the only non-duplicate in array
Variation of the previous question.
Find the two numbers with odd occurrences in an unsorted array
Given an unsorted array that contains even number of occurrences for all numbers except two numbers. Find the two numbers which have odd occurrences.
Naive
Use hashmap to store the frequency.
Time Complexity: $O(n)$
Auxiliary Space: $O(n)$
Using XOR
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> twoOddNum(int arr[], int n)
{
int XOR = 0, ans1 = 0, ans2 = 0;
for(int i=0; i<n; i++)
XOR = XOR ^ arr[i];
int rsb = XOR & ~(XOR-1);
for(int i=0; i<n; i++)
if(arr[i] & rsb)
ans1 = ans1 ^ arr[i];
else
ans2 = ans2 ^ arr[i];
return {max(ans1, ans2), min(ans1, ans2)};
}
Time Complexity: $O(n)$
Auxiliary Space: $O(1)$
Find the element that appears once
Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once.
Naive
Use hashmap to store the frequency.
Time Complexity: $O(n)$
Auxiliary Space: $O(n)$
Using XOR
use the fact that a ^ a = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int getSingle(int arr[], int n)
{
int ones = 0, twos = 0;
int common_bit_mask;
for (int i = 0; i < n; i++) {
twos = twos | (ones & arr[i]);
ones = ones ^ arr[i];
common_bit_mask = ~(ones & twos);
ones &= common_bit_mask;
twos &= common_bit_mask;
}
return ones;
}
Time Complexity: $O(n)$
Auxiliary Space: $O(1)$
Power Set
Given an unsorted array that contains even number of occurrences for all numbers except two numbers. Find the two numbers which have odd occurrences.
1
2
3
4
5
6
7
8
9
10
11
12
vector<string> AllPossibleStrings(string s){
vector<string> ans;
int counter, j, si = s.length(), pow_si = pow(2, si);
for (counter = 0; counter < pow_si; counter++) {
string word;
for (j = 0; j < si; j++)
if (counter & (1 << j))
word += s[j];
ans.push_back(word);
}
return ans;
}
Time Complexity: $O(n \times 2^n)$
Auxiliary Space: $O(1)$