CODEWITHSUNDEEP
algorithmassembly
whd
whd

Reputation: 1861

Generate any number using Incrementation and mult by 2

I'm looking for algorithm working in loop which will generate any natural number n with using only incrementation and multiplication by 2 well trivial way is known (increment number n times) but I'm looking for something a little bit faster. Honestly I don't even know how I should start this.

Upvotes: 0

Views: 79

Answers (2)

ssh
ssh

Reputation: 195

One way of doing this is to go backwards. If it's an odd number, subtract one. If it's even, divide by 2.

while(n > 0) {
   n & 1 ? n &= ~1 : n >>= 1;
}

Upvotes: 0

Drew McGowen
Drew McGowen

Reputation: 11706

Basically, what you want to do is shift in the bits of the number from the right, starting with the MSB.

For example, if your number is 70, then the binary of it is 0b1000110. So, you want to "shift in" the bits 1, 0, 0, 0, 1, 1, 0.

To shift in a zero, you simply double the number. To shift in a one, you double the number, then increment it.

if (bit_to_be_shifted_in != 0)
    x = (x * 2) + 1;
else
    x = x * 2;

So, if you're given an array of bits from MSB to LSB (i.e. from left to right), then the C code looks like this:

x = 0;
for (i = 0; i < number_of_bits; i++)
{
    if (bits[i] != 0)
        x = x * 2 + 1;
    else
        x = x * 2;
}

Upvotes: 3

Related Questions