Programming: Minimum steps required to convert a binary number to zero

Question

I was working on a programming exercise and was stuck on figuring out the correct algorithm. Here is the problem:

Given a decimal number, how many minimum possible steps are required to convert this to zero provided:

1. Change the bit i if the next bit i+1 is '1' and all the other bits i+2 and later are 0
2. Change the last bit without restriction

For example:

if input is (8)Base10 = (1000)Base2, then the steps taken are:

1000→1001→1011→1010→1110→1111→1101→1100→0100→0101→0111→0110→0010→0011→0001→0000

total 15 steps are required.

Complete the following definition:

int minStepsRequired(long number)

It's ok to get a pseudo code or just the algorithm. This is not a homework or assignment.

Answer 1

This is a wonderful problem for a recursive algorithm.

If the length of the binary representation is 0, you can already tell the answer. Or if length 0 is not allowed, then if the length is 1 you tell the answer depending on whether that one bit is 0 or 1.

If the length is longer than 1:

• If the first bit is 0, the answer is the same as it would be without that 0 bit. Remove it and call recursively to get the answer.
• If the first bit is 1, divide into three subproblems and find the step count for each:
  1. Establish a situation where you are allowed to change the leading 1 to 0. This means it should be followed by a 1 and then all 0s. Write a recursive auxiliary algorithm for this. It is going to be quite similar to the main algorithm, and likely they can share some logic.
  2. Flip the 1 to 0 (1 step)
  3. Convert the remaining bits bits to 0. Another recursive call.

The algorithm may take a long time. It is actually counting the steps, so takes time proportional to the number of steps, which I think is roughly proportional to the input number. Your method takes a long argument, but with my algorithm for large long values it may not terminate witin the lifetime of the computer it is running on. Also the number of steps may overflow an int and even a long (if the input is a negative long value).

The fast way

The following solution doesn’t require recursion and runs in constant time. I can’t explain properly how it works, which is a serious problem if we want to use it for something. I played with some examples, saw a pattern and generalized it. By contrast IMHO some of the beauty of the recursive solution above is that it is straightforward to understand (if you understand recursion).

Example: Input 8 or 1000 binary. Result 15 or 1111 binary. The pattern is: each bit of the result is the XOR of the previous bit of the result and the bit in the same position in the input. So from 1000 just copy the front bit, 1. The following bit is 1 XOR 0 = 1, where 1 is the front bit of the result and 0 is taken from the input. The remaining two bits are calculated the same way.

A longer example so you can check if you understood:

Input:  115 = 1110011
Result:       1011101 = 93

Or in code:

static BigInteger calculateStepsRequired(long number) {
    // Take sign bit
    int bit = number < 0 ? 1 : 0;
    BigInteger result = BigInteger.valueOf(bit);
    for (int i = 0; i < 63; i++) {
        number = number << 1;
        int sign = number < 0 ? 1 : 0;
        bit = (bit + sign) % 2;
        result = result.shiftLeft(1).add(BigInteger.valueOf(bit));
    }
    return result;
}

I have checked this method against my own implementation of the first algorithm above using various inputs up to 100 000 000, and they always agree, so I believe that the fast method is correct too. I still suggest that you should code, run and test it to verify that I got it right.