Sum of bit differences among all pairs

Problem: Given an integer array of n integers, find sum of bit differences in all pairs that can be formed from array elements.

Bit difference of a pair (x, y) is count of different bits at same positions in binary representations of x and y. For example, bit difference for 2 and 7 is 2. Binary representation of 2 is 010 and 7 is 111 ( first and last bits differ in two numbers).

For example:

Input:  arr[] = {1, 3, 5}
Output: 8
All pairs in array are (1, 1), (1, 3), (1, 5)
                       (3, 1), (3, 3) (3, 5),
                       (5, 1), (5, 3), (5, 5)
Sum of bit differences =  0 + 1 + 1 +
                          1 + 0 + 2 +
                          1 + 2 + 0 
                       = 8

Method 1: A Simple Solution is to run two loops to consider all pairs one by one. For every pair, count bit differences. Finally return sum of counts.

int sumBitDifferences(int arr[], int n)
{
    /* initialize result */
    int ans = 0;

    /* selecting pair of numbers using 2 loops */
    for(int i = 0; i < arr.size(); i++) 
    {
        for(int j = 0; j < arr.size(); j++) 
        {
            /* diff is zero for pair with same numbers, 
               hence ignore */
            if(arr[i] != arr[j]) 
            {
                /* xor gives the diff between two numbers */
                int xor = arr[i] ^ arr[j]; 

                /* setbits for the diff between two numbers */
                while(xor > 0) 
                {
                    xor &= xor - 1;
                    ans++;
                }
            }
        }
    }
    return ans;
}

Time complexity: O(n²).

Method 2: An Efficient Solution can solve this problem in O(n) time using the fact that all numbers are represented using 32 bits (or some fixed number of bits). The idea is to count differences at individual bit positions. We traverse from 0 to 31 and count numbers with i’th bit set. Let this count be ‘count’. There would be “n-count” numbers with i’th bit not set. So count of differences at i’th bit would be count * (n-count) * 2.

int sumBitDifferences(int arr[], int n)
{
    /* initialize result */
    int ans = 0;

    /* traverse over all bits */
    for (int i = 0; i < 32; i++)
    {

        /* count number of elements with i'th bit set */
        int count = 0;

        for(int j = 0; j < n; j++)
        {
            if( (arr[j] & (1 << i)) )
                count++;
        }

        /* Add "count * (n - count) * 2" to the answer */
        ans += (count * (n - count) * 2);

    }

    return ans;

}

Time complexity: O(n).

Count set bits in an integer

Problem: Write an efficient program to count number of 1s in binary representation of an integer.

For example:

Input: n = 5
Output: 2
Binary representation of 5 is (101). We see it has 2 set bits.

Input: n = 13
Output: 3
Binary representation of 13 is (1101). We see it has 3 set bits.

Method 1: Simple Method is to loop through all bits in the integer and check if a bit is set. If it is then increment the set bit count.

#include<bits/stdc++.h>
using namespace std;

/* function to get no of set bits in number */
int countSetBits(int n)
{
    int count = 0;
    while(n)
    {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

/* driver function */
int main()
{
    int n = 10;

    cout<<countSetBits(n)<<"\n";

    return 0;
}

Output:

2

Time Complexity: (-)(logn) (Theta of logn)

Method 2: We can count bits in O(1) time using lookup table.

#include<bits/stdc++.h>
using namespace std;

/* function to get no of set bits in number */
int countSetBits(int n)
{
    int count = 0;
    while(n)
    {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

/* driver function */
int main()
{
    int n = 10;

    cout<<countSetBits(n)<<"\n";

    return 0;
}

Output:

2
3

Time Complexity: O(1)

Note:  In GCC, we can directly count set bits using __builtin_popcount().

---

References:

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable

Convert a decimal number to binary number

Problem: Given a number, write a program to convert it into binary form.

For example:

Input: n = 499
Output: 111110011

Input: n = 5
Output: 101

Input: n = 25
Output: 11001

How to convert a decimal to binary?

Binary representation of 25 is (11001)₂

Method 1: Recursive

• if num > 1 
• push num on stack 
• do a recursive call on 'num / 2' 
• pop num from stack, divide it by 2 and print it's remainder

#include<bits/stdc++.h>
using namespace std;

void binary(int n)
{
    if (n > 1)
        binary(n/2);
 
    cout<<n%2;
}

/* driver fucntion */ 
int main(void)
{
    int num = 499;

    binary(num);
    cout<<"\n";    

    return 0;
}

Output:

111110011

Method 2: iterative

#include <bits/stdc++.h>
using namespace std;

/* driver fucntion */
int main()
{
    int n = 5;
    string ans = "";

    while(n > 0)
    {
        /* if reminder is 1, append to ans */
        if(n%2!=0)
            ans += "1";
        else
            ans += "0";
        n/=2;
    }

    /* reverse the string to get required answer */
    reverse(ans.begin(), ans.end());

    cout<<ans<<"\n";

    return 0;
}

Output:

101

Find the nth bit of a number

Problem: Given a numbers n and k. Write a program to print the value of kth bit in the binary representation of the number.

For example:

Input: n = 10
       k = 2
Output: 1
The binary representation of 10: (1010)
2nd bit is 1.

Method 1: To get the nth bit of any number we just need to right shift the number n times and then perform bitwise AND operation with the shifted number and 1. In general you may say (number >> n) & 1.

• 0 & 1 = 0 
• 1 & 0 = 0 
• 1 & 1 = 1

#include <bits/stdc++.h>
using namespace std;

/* driver function*/
int main() 
{
    int n = 10;
    int k = 2;

    /* we did k - 1 because, the bit position starts from 0 */
    cout<<((10 >> (k - 1)) & 1)<<"\n";
    
    return 0;
}

Output:

1

Reverse bits of a given 32 unsigned bits integer

Problem: Given an unsigned integer, reverse all bits of it and return the number with reversed bits.

For example:

Input: n = 43261596
Output: 964176192
The binary representation of 43261596 is 00000010100101000001111010011100.
Reversing the bits we get, 00111001011110000010100101000000 which is equivalent to 964176192.

Input: n = 1
Output: 2147483648
The binary representation of 43261596 is 00000000000000000000000000000001.
Reversing the bits we get, 10000000000000000000000000000000 which is equivalent to 2147483648.

The easiest and most efficient approach is reversing bit by bit.

#include <bits/stdc++.h>
using namespace std;

/* function return the reversed bits integer */
unsigned int revBits(unsigned int num)
{
    unsigned rev_num = 0;
    int siz = sizeof(num) * 8;

    for (int i = 0; i < siz; i++)
    {
        rev_num <<= 1;
        rev_num |= num & 1;
        num >>= 1; 
    }

    return rev_num;
}

/* driver function */
int main()
{
    int unsigned a;
   
    a = 1;
    cout<<revBits(a)<<"\n";

    a = 105;
    cout<<revBits(a)<<"\n";

    return 0;
}

Output:

2147483648

2516582400

Time Complexity: O(logn) and Space Complexity: O(1)

Find two odd occurring element in an unsorted array

Problem: Given an array of integers, each number in the array occur even number of times except two numbers that occur number of times. Find both odd appearing element without using any extra memory.

For example:

Input: arr = {4, 3, 6, 2, 4, 2, 3, 4, 3, 3}
Output: 4 and 6

Input: arr = {12, 23, 34, 12, 12, 23, 12, 45}
Output: 34 and 45

Input: arr = {4, 4, 100, 5000, 4, 4, 4, 4, 100, 100}
Output: 100 and 5000

A Naive method to solve this problem is to run two nested loops. The outer loop picks an element and the inner loop counts the number of occurrences of the picked element. If the count of occurrences is odd then print the number. The time complexity of this method is O(n²).

Other improved method is to use sorting to get the odd occurring numbers in O(nLogn) time. First sort the numbers using an O(nLogn) sorting algorithm like Merge Sort, Heap Sort, quickSort, etc. Once the array is sorted, all we need to do is a linear search of the array and print the odd occurring number.

We can also use hashing to solve this problem in O(n) time. The idea is to traverse the array and maintain frequency of each element in a hash table. After all array elements are processed, we return the elements with odd frequencies. The problem with this approach is that it requires O(n) extra space.

There is a better approach to solve this problem using bitwise XOR in O(n) time complexity and O(1) extra space. We know that if we XOR a number with itself odd number of times the result is number itself, otherwise if we XOR a number even number of times with itself, the result is 0. Also XOR with 0 is always the number itself.

• XOR of any number n with itself gives us 0, i.e., n ^ n = 0 
• XOR of any number n with 0 gives us n, i.e., n ^ 0 = n 
• XOR is cumulative and associative. 

So, if we take XOR of all elements present in the array, even appearing elements will cancel out each other and we are left with XOR of x and y (x ^ y) where x and y are two odd appearing elements. 

Finding x and y :

Let result = (x ^ y) We know that any set bit in result will be either set in x or y (but not in both as a bit will only set in result when it is set in one number and unset in the other). For example, if x = 6 (0110) and y is 15 (1111), then result will be (1001), the two set bits in result indicate that the corresponding bits in x and y are different.

The idea is to consider the rightmost set bit in result (or any other set bit) and split the array into two sub-arrays –

• All elements that have this bit set. 
• All elements that have this bit unset. 

As this rightmost bit is set in one number and unset in the other, we will have one odd appearing element in each sub-array. Basically we have isolated trait of one number with other so that both x and y will go to different sub-array. Now we iterate each sub-array once more, do XOR on each element of the sub-array and the result will be the odd appearing element present in the sub-array (since even appearing elements will cancel each other).

#include <bits/stdc++.h>
using namespace std;

pair<int, int> findOdd(int arr[], int n)
{
    int result = 0;

    /* taking XOR of all array elements */
    for (int i = 0; i < n; i++)
        result = result ^ arr[i];

    /* finding position of the rightmost set bit in result */
    int k = log2(result & -result);

    /* x and y are two odd appearing elements */
    int x = 0, y = 0;

    /* split the array into two sub-arrays */
    for (int i = 0; i < n; i++)
    {
        /* elements that have k'th bit 1 */
        if (arr[i] & (1 << k))
            x = x ^ arr[i];

        /* elements that have k'th bit 0 */
        else
            y = y ^ arr[i];
    }

    return make_pair(x, y);
}

/* Driver function */
int main()
{
    int arr1[] = { 4, 3, 6, 2, 4, 2, 3, 4, 3, 3 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);

    pair<int, int> p1 = findOdd(arr1, n1);
    cout<< p1.first << " and " << p1.second <<"\n";

    int arr2[] = { 12, 23, 34, 12, 12, 23, 12, 45 };
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    pair<int, int> p2 = findOdd(arr2, n2);
    cout<< p2.first << " and " << p2.second <<"\n";

    int arr3[] = {4, 4, 100, 5000, 4, 4, 4, 4, 100, 100};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);

    pair<int, int> p3 = findOdd(arr3, n3);
    cout<< p3.first << " and " << p3.second <<"\n";

    return 0;
}

Output:

6 and 4
45 and 34
100 and 5000

Count number of bits to be flipped to convert A to B

Problem: Given two numbers A and B. Write a program to count number of bits needed to be flipped to convert A to B.

For example:

Input: A = 12 and B = 22
Output: 3

Binary representation of 12 is 001100
Binary representation of 22 is 010110

Here we need to flip 3 bits in A to convert it to B.

Input: A = 10 and B = 20
Output: 4

Binary representation of 10 is 001010
Binary representation of 20 is 010100

Here we need to flip 4 bits in A to convert it to B.

Approach: Here we will use XOR operator to calculate our result.

• Calculate XOR of A and B. 
• x = A ^ B 
• Count the set bits in x calculated above. 

Following is the implementation of above approach:

#include <bits/stdc++.h>
using namespace std;

/* function to calculate number of flips */
int numFlip(int A, int B)
{
    /* A xor B */
    int x = A ^ B;

    int count = 0;
    while(x)
    {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

/* driver function */
int main()
{
    int A, B;

    A = 12; B = 22;
    cout<<numFlip(A, B)<<"\n";

    A = 10; B = 20;
    cout<<numFlip(A, B)<<"\n";

    return 0;
}

Output:

3
4