Bitwise Operations (Part-2)

Bitwise GCD:

Bitwise GCD is applicable only for unsigned int. It's 60% faster than normal numeric gcd algorithm. The quick short implementation of bitwise GCD is:

public int gcd(int a, int b) {
    while(b) b ^= a ^= b ^= a % b;
    return a;
}

Ref: https://en.wikipedia.org/wiki/Binary_GCD_algorithm

Set representation using integers:

Consider, S = {a, b, c, d}. Then binary number 0101 (5) denotes the subset X = {b, d}.

If,

  • A set is represented by a
  • B set is represented by b

Then,

  1. a & b means intersaction of sets.
  2. a | b means union of sets
  3. a ^ b means symmetric difference of two sets
  4. a ^ (a & b) means the set of elements belongs to only A.
All Subsets of a given subset:

Consider you are implementing sets using binary representation of an integer. Each bit represents existance an element of set. For example, Decimal = 22, Binary = 10110 is a subset which has 3 elements. Set bits represents that element exists. In this case, 1st, 2nd and 4th element (0 based) exist in the subset. Our goal is to find all subsets of the given subset 22 (10110).

At first lets look over the subsets of 22 (10100). Since there are 3 elements, there will be 23 subsets:

00000 = 0
00010 = 2
00100 = 4
00110 = 6
10000 = 16
10010 = 18
10100 = 20
10110 = 22

Here's the very elegant way to generate all above subsets using bitwise operation:

public void printSubsets(int N) {
    int X = N;
    while (true) {
        System.out.println(X);
        if (X == 0) break;
        X = (X - 1) & N;
    }
}

Explanation:

First observation is - value of all subsets will be less than the given subset. Lets write down all values less than 22(10110).

10110 = 22
10101 = 21
10100 = 20
10011 = 19
10010 = 18
10001 = 17
10000 = 16
01111 = 15
01110 = 14
01101 = 13
01100 = 12
01011 = 11
01010 = 10
01001 = 9
01000 = 8
00111 = 7
00110 = 6
00101 = 5
00100 = 4
00011 = 3
00010 = 2
00001 = 1
00000 = 0

Second observation is - All of the above subsets aren't valid. For example, 10101 = 21 has 0th bit set while the given subset has 0th bit off. To overcome this problem we have to do bitwise AND with the original subset N. That will give us next immediate subsets less then current subset.

Blog Comments powered by Disqus.

Next Post Previous Post