## Table Of Content

- Check Kth bit is set or not
- Count set bit
- Detect if two integers have opposite signs
- Swap two numbers without using temp variable
- Is power of 2
- Add two numbers without using arithmetic operators
- Find odd occuring number
- Find the only non-duplicate in array
- Find the two numbers with odd occurrences in an unsorted array
- Find the element that appears once
- Power Set

## 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$

```
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)

```
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)

```
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)

```
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.

```
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.

```
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.

```
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.

```
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.

```
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.

```
int rsb = a & ~(a-1);
```

```
110100 (52)
110011 (51)
001100 ~(51)
110100 (52)
& 001100 ~(51)
000100 (Right most set bit)
```

### Binary operators #

#### « (Left Shift) #

```
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.

- b « a $\implies b \times 2^a $

#### » (Right Shift) #

```
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.

- 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 #

```
bool kthbit(int k, int n){
if (n & (1 << (k - 1)))
return true;
return false;
}
```

**Time Complexity:** $O(1)$

#### Using right shift #

```
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 #

```
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 #

```
int setBits(int N) {
int count = 0;
while (N) {
N &= (N - 1);
count++;
}
return count;
}
```

**Time Complexity:** $O(logn)$

#### Using Lookup Table #

```
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 #

```
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.

```
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 #

```
void swapped(int* x, int* y)
{
x = x + y;
y = x - y;
x = x - y;
}
```

#### Using XOR #

Use the fact `x ^ x = 0`

```
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 #

```
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 #

```
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 #

```
bool isPowerofTwo(long long n){
return n && (!(n&(n-1)));
}
```

**Time Complexity:** $O(1)$

#### Using log #

```
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

```
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`

```
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 #

```
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`

```
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.

```
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)$