Most binary combinations from 4 bits, with single change per bit

Question

I have 4 binary bits

Bit 3  Bit 2  Bit 1  Bit 0

Normally the answer is simple: 2^4, or 16 different combinations; and it would looks something like the following:

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

However, The LSB (Bit 0) changes state every iteration.

I need an algorithm where the state of a bit only changes once through all the iterations; i.e, I need all my bits to act like the MSB (Bit 3).

How can I do this?

Edit

It seems that most people are converging to there being only 5 possible solutions. However this assumes there is a starting point for the value and an ending point. This doesn't matter so I'm going to give a real world scenario to better explain.

Suppose I have an digital alarm clock that gives me 4 outputs. Each output can be programmed to go on at a certain time and off at a certain time and are programmed independent of each other, eg. I can program output 1 to go on at 1 am and off at 3 am, while I can program output 2 to go on at 7 pm and off at 2 am. There are no restrictions to how long each output can stay on.

Now I want to hook this alarm clock to a computer and get as close as possible to the current correct time. i.e If the clock says the time is 2:15 pm, my computer knows that the alarm is within the 12 pm to 6 pm range for example. I want to be able to get the smallest possible range. Whats the smallest possible range I can get?

Answer 1

1. There are 4 bits.
2. Each bit may change state only once.
3. For each new value, at least one of the bits must have changed state from the previous value.

Therefore, you can have at most 4 state changes, and at most 5 different values.

Example:

0000 -> 0001 -> 0011 -> 0111 -> 1111

Edit:

Very well, let's restate from what you mean rather than from what you say.

1. There are 4 bits.
2. Each bit may change state only twice. (once from 0 to 1, and once from 1 to 0)
3. For each new value, at least one of the bits must have changed state from the previous value.

Therefore, you can have at most 8 state changes, and at most 8 different values (since the last state change necessarily brings all bits back to their initial state)

Example:

0000 -> 0001 -> 0011 -> 0111 -> 1111 -> 1110 -> 1100 -> 1000 -> 0000

So, by setting the outputs for: 3 AM - 3 PM, 6 AM - 6 PM, 9 AM - 9 PM and noon - midnight, you can determine which 3-hour period it is from the outputs. I'd suggest plugging wires into the visual output instead.

Answer 2

You want a Gray Code. Look about half way down for "Constructing an n-bit gray code".

Answer 3

I believe it is impossible to cycle though all possible bit patterns with such a restriction.

If you have an n-bit idea, you can cycle though a total of (n+1) states before having to flip a bit you've already flipped.

For example, in a 3-bit example, if you start with 111, you get

111
110
100
000

And then you're forced to flip one you've already flipped to get a new state.

Answer 4

Based on your alarm clock example I assume you need to finish on the combiation you started on, and that each bit can be cycled on then off only once, e.g.

0000 -> 0001 -> 0011 -> 0111 -> 1111 -> 1110 -> 1100 -> 1000 -> 0000

The number of steps is twice the number of bits, so with 4 bits you could get the current time to within a 3 hour range.

Answer 5

You want each bit to change only once?

Like:

0000 -> 0001 -> 0011 -> 0111 -> 1111 

In that case you can use a simple counter where the delta is multiplied by 2 each iteration (or shift left).

Answer 6

If Gamecat got you correctly, your bitmask values will be:

 1 - 1 
 2 - 1 
 4 - 1
 8 - 1
 16 - 1
 etc.
 2^i - 1

or, using shifts: (1 << i) - 1 for i in 0..

Answer 7

"I need an algorithm where the state of a bit only changes once through all the iterations"

If the above statement is taken literally, then there are only five states per iteration, as explained in other posts.

If the question is "How many possible sequences can be generated?", then:

Is the first state always 0000?

If not, then you have 16 possible initial states.

Does order matter?

If yes, then you have 4! = 24 possible ways to choose which bits to flip first.

So, this gives a total of 16*24 = 384 possible sequences that can be generated.

Answer 8

Looking back at the original question i think i understand what you mean

simply whats the smallest amount of bits you can use to program a clock, based on the amount of possible bit combinations

the first question is how many sequences are required.

60Secs x 60 Mins x 24hrs = 86400 (combinations required) the next step is to work out how many bit are required to produce at least 86400 combinations

if somebody know the calculation to

how many bits can produce 86400 combinations then thats your answer. hopefully there is a formula online somewhere for this calculation

Answer 9

Here is an example to how you can keep a bit from only being flipped once. Not knowing all the parameter of you system it is not easy to give an accurate example but here is one anyway.

char bits = 0x05;
flipp_bit(char bit_flip)
{
    static char bits_flipped=0;
    if( (bits_flipped & bit_flip) == 0)
    {
        bits_flipped |= bit_flip;
        bits ^= bit_flip;
    }
}

Flipping with this function will only allow one flip on each bit.