Home DSA Part 3: Bit Manipulation
Post
Cancel

DSA Part 3: Bit Manipulation

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

loading
Binary representation of $11_{10}$

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.

loading
Binary representation of 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.

loading
Binary representation of 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.

loading
Binary representation of –2,147,483,648

$\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.

loading
Binary representation of 2,147,483,647

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

OperatorOperation
&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 & 00
1 & 00
1 & 11

| - Bitwise OR

Performs bitwise OR on every bit of the operands.

1
2
  int a = 7, b = 9;
  cout << 7 | 9 << endl;
  
0 | 00
1 | 01
1 | 11

^ - Bitwise XOR

Performs bitwise XOR on every bit of the operands.

1
2
  int a = 7, b = 9;
  cout << 7 ^ 9 << endl;
  
0 ^ 00
1 ^ 01
1 ^ 10
  • 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;
  
~01
~10
  • ~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)$

This post is licensed under CC BY 4.0 by the author.

Google Codejam 2022

Intro to ML Part 1: Introduction