CODEWITHSUNDEEP
csegmentation-faultbit-manipulation
LulzCow
LulzCow

Reputation: 1229

Why is my bitwise division function producing a segmentation fault?

My code is below, and it works for most inputs, but I've noticed that for very large numbers(2147483647 divided by 2 for a specific example), I get a segmentation fault and the program stops working. Note that the badd() and bsub() functions simply add or subtract integers respectively. 

unsigned int bdiv(unsigned int dividend, unsigned int divisor){  
    int quotient = 1; 
    if (divisor == dividend)
    {
        return 1; 
    }
    else if (dividend < divisor)
    {   return -1; }// this represents dividing by zero

    quotient = badd(quotient, bdiv(bsub(dividend, divisor), divisor));

    return quotient;
}

I'm also having a bit of trouble with my bmult() function. It works for some values, but the program fails for values such as -8192 times 3. This function is also listed. Thanks in advance for any help. I really appreciate it!

int bmult(int x,int y){
    int total=0;
    /*for (i = 31; i >= 0; i--)
    {
        total = total << 1;
        if(y&1 ==1)
        total = badd(total,x);
    }
    return total;*/ 
    while (x != 0)
    {
        if ((x&1) != 0)
        {
            total = badd(total, y);
        }
        y <<= 1;
        x >>= 1;
    }
    return total; 
}

Upvotes: 0

Views: 846

Answers (2)

Alexey Frunze
Alexey Frunze

Reputation: 62106

In the multiplication, this line is going to overflow and truncate y, and so badd() will be getting wrong inputs:

y<<=1;

This line:

x>>=1;

Is not going to work for negative x well. Most compilers will do a so-called arithmetic shift here, which is like a regular shift with 0 shifted into the most significant bit, but with a twist, the most significant bit will not change. So, shifting any negative value right will eventually give you -1. And -1 shifted right will remain -1, resulting in an infinite loop in your multiplication.

You should not be using the algorithm for multiplication of unsigned integers to multiply signed integers. It's unlikely to work well (if at all) if it uses signed types in its core.

If you want to multiply signed integers, you can first implement multiplication for unsigned ones, using unsigned types. And then you can actually use it for signed multiplication. This will work on virtually all systems because they use 2's complement representation of signed integers.

Examples (assuming 16-bit 2's complement integers):

-1 * +1 -> 0xFFFF * 1 = 0xFFFF -> convert back to signed -> -1
-1 * -1 -> 0xFFFF * 0xFFFF = 0xFFFE0001 -> truncate to 16 bits & convert to signed -> 1

In the division the following two lines

else if (dividend < divisor)
{   return -1; }// this represents dividing by zero

Are plain wrong. Think, how much is 1/2? It's 0, not -1 or (unsigned int)-1.

Further, how much is UINT_MAX/1? It's UINT_MAX. So, when your division function returns UINT_MAX or (unsigned int)-1 you won't be able to tell the difference, because the two values are the same. You really should use a different mechanism to notify the caller of the overflow.

Oh, and of course, this line:

quotient = badd(quotient, bdiv(bsub(dividend, divisor), divisor));

is going to cause a stack overflow when the quotient is expected to be big. Don't do this recursively. At the very least, use a loop instead.

Upvotes: 1

jpm
jpm

Reputation: 3155

The problem with your bdiv is most likely resulting from recursion depth. In the example you gave, you will be putting about 1073741824 frames on to the stack, basically using up your allotted memory.

In fact, there is no real reason this function need be recursive. I could quite easily be converted to an iterative solution, alleviating the stack issue.

Upvotes: 1

Related Questions