implementing subtraction with bitwise shifts and increments

Is there an algorithm that can be use to subtra开发者_StackOverflow社区ct 1 from a number using only increments (++ in C) and left bitwise shifts (<< in C) ?

EDIT: I am using type unsigned char

Thanks in advance

---

You can do it with just the ++ operator. Loop for UCHAR_MAX iterations. Quite inefficient though:

unsigned char c = 42;
unsigned char i = 0;

while (++i)
{
    ++c;
}
// c is now equal to 41

LIVE DEMO

---

Yes. You need to approach a number n such that n mod 255 equals originalNumber - 1. The easiest way to do that would be to add 255 to your number. This can be accomplished by 255 applications of the ++ operator or more intelligently by shifting until adds are necessary.

Edit As Requested:

unsigned char c = 77;
unsigned char i = 0;


if(c < 128)
{
    i = c;
    c = c << 1;
}
while(++i)
{
    ++c;
}
// c == 76

I realize this requires a < "operator" but lets be honest, if a computer can shift, it can less than. Otherwise this optimization is not possible. Bear in mind this is also going to shift a maximum of 1 time, which is still better then nothing for numbers in the range of 3-127. In order to shift more then that, we would need a plain old + operator for our counter i. Although...I don't know of ANY computer that can't add.

---

This uses + as well, so it's not as deviously awesome as Paul R's answer.

unsigned char subtract_one(unsigned char value)
{
    unsigned char addend= 0;

    unsigned char old_addend;

    do
    {
        old_addend= addend;
        addend= addend << 1;
        addend++;
    }
    while (old_addend!=addend); // stops when addend==-1;

    return value + addend;
}

---

You can implement addition using the bitwise operators as well, and then compound that with the other 2 solutions to get a solution that doesn't require the "+" operator:

function add(int a, int b) {
   int x, y;
   do {
       x = a & b;
       y = a ^ b;
       a = x << 1;
       b = y;
   } while (a);
   return b;
}