by Priyanshu Tiwari

## Table Of Content

• Bitwise Operators
• Problems
• ## 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;
for (int i = 0; i < n; i++) {
twos = twos | (ones & arr[i]);
ones = ones ^ arr[i];
}

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