What is wrong with my program?

I cannot figure out what is wrong. I spent a few hours trying to debug this. I am compiling with gcc -m32 source.c -o source

How else can I approach this when debugging? Right now, I am isolating the code in many different ways and everything is working the way I expect but its working the wrong way when I have it all together.

This program takes an input and then looks for the highest position with the 1 bit.

I re开发者_StackOverflow中文版moved my code for now.

---

in bitsearch, you are storing num in eax, you store a special value in edx in order to perform check. check is testing if the highest bit is set (indicating a negative number), and exits if its the case...

the andl instruction in check stores the result of the operation inside the second operand (eax), so the result overwrites num.

then in zero you are using edx to perform your computation... edx contains the special value of the start of the function, so your result will always be wrong.

now at the end of zero, you are going back to check, but the check is unnecessary here, you should loop back to zeroinstead...

---

Does the bit-search need to be implemented in assembly? A simple for loop can accomplish the same task, and is much more readable:

int num = 10;
int maxFound = -1;
for (int numShifts = 0; numShifts < 32 && num != 0; numShifts++) {
    if ((num & 1) == 1) {
        maxFound = numShifts;
    }
    num = num >> 1;
}
//the last position that had a 1 will be in maxFound

---

There's a neat bit-fiddling trick: x & -x isolates the last 1-bit. The following C program uses a lookup table based on de Bruijn sequences to compute the number of trailing (!) zeros of a number in constant (!) time:

unsigned int x;  // find the number of trailing zeros in 32-bit x
int r;           // result goes here
int table[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = table[((uint32_t)((x & -x) * 0x077CB531U)) >> 27];

Doing this in assembly language (which I stopped learning by the age of 16) should be no problem. Now all you have to do is to reverse the bits in num and apply the technique described above.

I wrote a paper about the trick described above, but unfortunately it's not available on the web. If you're interested, I can send it to you (or anyone else who's interested) by email.

---

My assembly knowledge is a little rusty, but it seems to me like bitsearch is overly complicated. How about just rotating the number to the right and counting the times you need to do that until it's zero?