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?
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments