DSA Part 3: Bit Manipulation

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.

Practice

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.

Practice

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.

Practice

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.

Practice

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.

Practice

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.

Practice

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.

Practice

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.

Practice

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

Categories

Tags

Table Of Content

Binary Numbers #

Significant bits #

MSB #

LSB #

Signed and Unsigned 32-bit Int #

Unsigned Integer #

Minimum Possible Value #

Maximum Possible Value #

Signed #

2’s Complement #

Minimum Possible Value #

Maximum Possible Value #

Bitwise Operators #

Types of operators #

Unary operators #

& - Bitwise AND #

| - Bitwise OR #

^ - Bitwise XOR #

~ - Bitwise NOT #

RSB #

Binary operators #

« (Left Shift) #

» (Right Shift) #

Problems #

Check Kth bit is set or not #

Using left shift #

Using right shift #

Count set bit #

Naive #

Brian Kernighan’s Algorithm #

Using Lookup Table #

Detect if two integers have opposite signs #

Arithmetic comparison #

Using XOR #

Swap two numbers without using temp variable #

Arithmetic Operators #

Using XOR #

Is power of 2 #

Naive #

Brian Kernighan’s Algorithm #

Optimized #

Using log #

Add two numbers without using arithmetic operators #

Find odd occuring number #

Naive #

Using XOR #

Find the only non-duplicate in array #

Find the two numbers with odd occurrences in an unsorted array #

Naive #

Using XOR #

Find the element that appears once #

Naive #

Using XOR #

Power Set #