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
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).
When all the bits are set to 0.
$\rightarrow (2^{31} \cdot 0) + (2^{30} \cdot 0) + \ldots( 2^0 \cdot 0) = 0$
unsigned int mini = 0;
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)
unsigned int maxi = UINT_MAX;
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 ?
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. {: .prompt-tip }
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)
int mini = INT_MIN;
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)
int maxi = INT_MAX;
| Operator | Operation |
|---|---|
| & | AND |
| | | OR |
| ^ | XOR |
| » | Left Shift |
| « | Right Shift |
| ~ | NOT |
Performs bitwise AND on every bit of the operands.
int a = 7, b = 9;
cout << 7 & 9 << endl;
| 0 & 0 | 0 |
| 1 & 0 | 0 |
| 1 & 1 | 1 |
Performs bitwise OR on every bit of the operands.
int a = 7, b = 9;
cout << 7 | 9 << endl;
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Performs bitwise XOR on every bit of the operands.
int a = 7, b = 9;
cout << 7 ^ 9 << endl;
| 0 ^ 0 | 0 |
| 1 ^ 0 | 1 |
| 1 ^ 1 | 0 |
Inverts all bits of the operand.
int a = 7
cout << (~7) << endl;
| ~0 | 1 |
| ~1 | 0 |
~a $\implies$ INT_MAX - a (only for +ve integers)Subtracting 1 from a decimal number flips all the bits after the rightmost set bit including the rightmost set bit. {: .prompt-tip }
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. {: .prompt-tip }
int rsb = a & ~(a-1);
110100 (52)
110011 (51)
001100 ~(51)
110100 (52)
& 001100 ~(51)
000100 (Right most set bit)
int a = 7, b = 2;
cout << (b << a) << endl;
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.
int a = 7, b = 2;
cout << (b >> a) << endl;
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.
Given a number n, check if the Kth bit of n is set or not.
bool kthbit(int k, int n){
if (n & (1 << (k - 1)))
return true;
return false;
}
Time Complexity: $O(1)$
bool kthbit(int k, int n){
if ((n >> (k-1)&1))
return true;
return false;
}
Time Complexity: $O(1)$
Write a program to count the number of 1s in the binary representation of an integer.
int setBits(int N) {
int count = 0;
while(N){
count += (N & 1);
N = N >> 1;
}
return count;
}
Time Complexity: $O(n)$
int setBits(int N) {
int count = 0;
while (N) {
N &= (N - 1);
count++;
}
return count;
}
Time Complexity: $O(logn)$
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)$
Given two signed integers, write a function that returns true if the signs of given integers are different, otherwise false.
bool oppositeSigns(int x, int y)
{
return (x < 0) ? (y >= 0) : (y < 0);
}
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.
bool oppositeSigns(int x, int y)
{
return ((x ^ y) < 0);
}
Given two variables, x, and y, swap two variables without using a third variable.
void swapped(int* x, int* y)
{
x = x + y;
y = x - y;
x = x - y;
}
Use the fact x ^ x = 0
void swapped(int* x, int* y)
{
x = x ^ y;
y = x ^ y;
x = x ^ y;
}
Given a positive integer, write a function to find if it is a power of two or not.
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)$
int setBits(int N) {
if(!N) return false;
int count = 0;
while (N) {
N &= (N - 1);
count++;
}
return count == 1;
}
Time Complexity: $O(logn)$
bool isPowerofTwo(long long n){
return n && (!(n&(n-1)));
}
Time Complexity: $O(1)$
bool isPowerofTwo(long long n){
if(!n) return false;
return (ceil(log2(n)) == floor(log2(n)));
Time Complexity: $O(1)$
Write a function that returns sum of two integers. The function should not use any of the arithmetic operators
int Add(int x, int y)
{
while (y)
{
unsigned carry = x & y;
x = x ^ y;
y = carry << 1;
}
return x;
}
Given an array of positive integers. All numbers occur an even number of times except one number which occurs an odd number of times.
Use hashmap to store the frequency.
Time Complexity: $O(n)$
Auxiliary Space: $O(n)$
use the fact that a ^ a = 0
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)$
Variation of the previous question.
Given an unsorted array that contains even number of occurrences for all numbers except two numbers. Find the two numbers which have odd occurrences.
Use hashmap to store the frequency.
Time Complexity: $O(n)$
Auxiliary Space: $O(n)$
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)$
Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once.
Use hashmap to store the frequency.
Time Complexity: $O(n)$
Auxiliary Space: $O(n)$
use the fact that a ^ a = 0
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)$
Given an unsorted array that contains even number of occurrences for all numbers except two numbers. Find the two numbers which have odd occurrences.
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)$