undoing binary shift in C, gcc

ta0kira · 07-05-2007, 07:27 AM

Quote:

Originally Posted by atulsvasu

The possible confusion is because my search is not clear for you.
in 16-bit case, I check if the number is greater than 2^8 or not,
if yes, I rightshift by 8, Then I check if it is greater than 2^4 or
not, if yes shift 4, then if it is greater than 2^2 shift 2, then if
greater than 2^1 shift 1. Whenever I shift the number by somevalue I
increment the output by same quantity. It is almost a binary search,
you may wonder if comparison takes multiple cycles, it may but
machine can ensure even that is O(P(log(n))), if n is very large, moreover
it is not our concern. Our concern must be number of instructions.

Your code makes sense now, but it only checks for the highest-set bit and none other. As you stated, this will be very efficient for a high number, but here you essentially log2 the cycles but adds an additional 2 operations per cycle, and it must be accomplished three times to allow for second and possible third bits so it uses a max of 48 basic math operations (not including comparisons,) whereas checking one at a time can result in at most 16. The actual complexity of yours seems to be O(x log n) where x is the number of elements in the combination. Take this vs. O(n) and yours comes out ahead for very large numbers or low numbers of combined bits, but not with 16 bits. It looks like yours would come out ahead at 75 bits and above based strictly on number of arithmetic/assignment operations.
ta0kira

graemef · 07-05-2007, 07:06 PM

I follow the principle of never optimise unless you have to, and then when you do make it as specific as possible. I would make a few comments. First if possible write your code knowing the number of bits you number has, second if it makes sense avoid error checking, third do the smallest amount of work and then get out of there.

So with that in mind I would find the location of the highest bit, don't worry about any other bits or if there are more than two. I would also assume that the integer is a 16-bit number.

I would then use ta0kira's approach but reverse it, that is look for the largest bit first, additionally I'd use literals rather than constants. I would also remove the error checking and break out as soon as the condition has been met.

This would give something like:

Code:

int posn = 0;
if (val & 65536)
   posn = 16;
else if (val & 32768)
   posn = 15;
else if (val & 16384)
   posn = 14;
else if ...

Obviously you need to be sure that,
1) removing the error checking is acceptable, posn = 0 if there are no bits set.
2) all the bits are accounted for, adjusting the code appropriately

Metric of the algorithm, whilst big O is traditionally used to measure the efficiency of an algorithm, it only make sense when extrapolated to large numbers, here it is a small piece of data that is being examined and the fixed number of instructions per iteration do make an impact on the overall efficiency.

graemef · 07-05-2007, 07:40 PM

Dang, just read the OP again and spotted the comment

Code:

/* run another loop to find the second value, check that there are no more values *

So you need both bits, in which case I would suggest.
Repeat the code this time looking from the smallest bit.

Code:

int posn_low = 0;
if (val & 1)
   posn_low = 1;
else if (val & 2)
   posn_low = 2;
else if (val & 4)
   posn_low = 3;
else if ...

Finally if you want to check that there are no other bits set then, you can use something like:

Code:

if (val != ((1<<posn_high) + (1<<posn_low)))
/*error situation */

and also something like

Code:

if (posn_high == posn_low)
/*error situation */

You do have quite a few lines of code, but the number of instructions executed is optimal (I think)