CODEWITHSUNDEEP
calgorithm
Jagdish
Jagdish

Reputation: 1924

what can be the best algorithm to find numbers with only single set bit and whose sum is equal to given number?

Suppose i have one number 0b10110010,

I want to parse it in different numbers whose sum is equal to above number, All parsed numbers should have only single bit set.

 10000000  <-- num1
 + 100000  <-- num2
 +  10000  <-- num3
 +     10  <-- num4
----------
 10110010  <-- num1 + num2 + num3 + num4

What can be the best algorithm for this?

Upvotes: 1

Views: 86

Answers (1)

fuz
fuz

Reputation: 92994

Basically, something like this:

int i;
for (i = 1; i <= num && i != 0; i <<= 1) {
    if ((i & num) == 0)
        continue;

    /* i is part of the decomposition, do something with it */
    printf("0x%4x\n", i);
}

This iterates through all possible numbers with one bit set and ignores those for which the corresponding bit in num isn't set. The complexity is O(log num). There is also an O(k) solution where k is the number of 1 bits in num, the algorithm goes like this:

int i, n = num;
while (n != 0) {
    i = ((n - 1) & ~n) + 1;
    /* i is part of the decomposition */
    printf("%4x\n", i);
    n &= n - 1;
}

Consider the following diagram to understand how this works:

n             101101101010100000000
n - 1         101101101010011111111
~n            010010010101011111111
~n & (n - 1)  000000000000011111111
i             000000000000100000000
n & (n - 1)   101101101010000000000

In the last line, n &= ~i could also be used but that would force the compiler to retain the i variable for a bit longer than needed which may be less optimal for speed. Benchmark when in doubt.

My personal guess is that the second method is faster if num is sparse, i.e. only few bits are set in num. Due to its lower number of operations, you should use the first method if num is known to not be sparse.

Upvotes: 5

Related Questions