Большинство двоичных комбинаций из 4 бит, с одним изменением на бит

Question

У меня есть 4 двоичных бита

Bit 3  Bit 2  Bit 1  Bit 0

Обычно ответ прост:2^ 4, или 16 различных комбинаций;и это выглядело бы примерно следующим образом:

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

Однако LSB (бит 0) изменяет состояние на каждой итерации.

Мне нужен алгоритм, в котором состояние бита изменяется только один раз на протяжении всех итераций;то есть мне нужно, чтобы все мои биты действовали как MSB (бит 3).

Как я могу это сделать?

Редактировать

Похоже, что большинство людей сходятся к тому, что существует только 5 возможных решений.Однако это предполагает, что существует начальная точка для значения и конечная точка.Это не имеет значения, поэтому я собираюсь привести сценарий реального мира, чтобы лучше объяснить.

Предположим, у меня есть цифровой будильник, который выдает мне 4 выхода.Каждый выход может быть запрограммирован на включение в определенное время и выключение в определенное время и программируется независимо друг от друга, например.Я могу запрограммировать выход 1 на включение в 1 час ночи и выключение в 3 часа ночи, в то время как я могу запрограммировать выход 2 на включение в 7 часов вечера и выключение в 2 часа ночи.Нет никаких ограничений на то, как долго каждый выходной сигнал может оставаться включенным.

Теперь я хочу подключить этот будильник к компьютеру и установить его как можно ближе к текущему правильному времени.то есть, если часы показывают время в 14:15, мой компьютер знает, что будильник находится, например, в диапазоне от 12:00 до 18:00.Я хочу иметь возможность получить как можно меньший диапазон.Какой минимально возможный диапазон я могу получить?

Answer 1

1. Всего есть 4 бита.
2. Каждый бит может изменить состояние только один раз.
3. Для каждого нового значения по крайней мере один из битов должен иметь измененное состояние по сравнению с предыдущим значением.

Следовательно, у вас может быть не более 4 изменений состояния и не более 5 различных значений.

Пример:

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

Редактировать:

Очень хорошо, давайте переформулируем то, что вы имеете в виду, а не то, что вы говорите.

1. Всего есть 4 бита.
2. Каждый бит может изменять только состояние дважды.(один раз от 0 до 1 и один раз от 1 до 0)
3. Для каждого нового значения по крайней мере один из битов должен иметь измененное состояние по сравнению с предыдущим значением.

Следовательно, у вас может быть не более 8 изменений состояния и не более 8 различных значений (поскольку последнее изменение состояния обязательно возвращает все биты в их исходное состояние)

Пример:

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

Итак, установив выходные данные для:С 15:00 до 15:00, с 6:00 до 18:00, с 9:00 до 21:00 и с полудня до полуночи, вы можете определить, какой это 3-часовой период, по выходным данным.Вместо этого я бы предложил подключить провода к визуальному выводу.

Answer 2

Вам нужен серый код . Посмотрите на полпути вниз для & Quot; Построение n-битного серого кода & Quot;.

Answer 3

Я считаю, что невозможно циклически повторять все возможные битовые комбинации с таким ограничением.

Если у вас есть идея с n-битами, вы можете выполнить циклическое переключение в общей сложности (n + 1) состояний, прежде чем отразить бит, который вы уже перевернули.

Например, в 3-битном примере, если вы начнете с 111, вы получите

111
110
100
000

А затем вы вынуждены перевернуть тот, который вы уже перевернули, чтобы получить новое состояние.

Answer 4

Исходя из вашего примера с будильником, я предполагаю, что вам нужно закончить комбинацию, с которой вы начали, и что каждый бит можно включать и выключать только один раз, например

  

0000 - > 0001 - & GT; 0011 - & GT; 0111 - & GT; 1111   - GT &; 1110 - & GT; 1100 - & GT; 1000 - & GT; 0000

Количество шагов в два раза больше количества битов, поэтому с 4 битами вы можете получить текущее время с точностью до 3 часов.

Answer 5

Вы хотите, чтобы каждый бит менялся только один раз?

Нравится:

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

В этом случае вы можете использовать простой счетчик, где дельта умножается на 2 на каждой итерации (или сдвигается влево).

Answer 6

Если Gamecat правильно вас понял, ваши значения битовой маски будут:

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

или, используя смены:  (1 & Lt; & Lt; i) - 1 для i в 0 ..

Answer 7

& "Мне нужен алгоритм, в котором состояние бита изменяется только один раз за все итерации "

Если приведенное выше утверждение воспринимается буквально, то на одну итерацию приходится только пять состояний, как объяснено в других публикациях.

Если вопрос " сколько возможных последовательностей можно сгенерировать? " ;, тогда:

Всегда ли первое состояние 0000?

Если нет, то у вас есть 16 возможных начальных состояний.

Имеет ли значение заказ?

Если да, то у вас есть 4! = 24 возможных способа выбрать, какие биты переворачивать первыми.

Таким образом, это дает в общей сложности 16 * 24 = 384 возможных последовательностей, которые могут быть сгенерированы.

Answer 8

Оглядываясь на исходный вопрос, я думаю, что понимаю, что вы имеете в виду

просто наименьшее количество бит, которое вы можете использовать для программирования тактовой частоты, исходя из количества возможных битовых комбинаций

Первый вопрос: сколько требуется последовательностей?

60 секунд x 60 минут x 24 часа = 86400 (требуются комбинации) Следующий шаг - определить, сколько бит требуется для создания не менее 86400 комбинаций.

если кто-то знает расчет до

сколько бит может дать 86400 комбинаций, тогда это ваш ответ. надеюсь, где-то есть формула где-то для этого расчета

Answer 9

Вот пример того, как вы можете удержать бит от переворачивания только один раз. Не зная всех параметров вашей системы, нелегко привести точный пример, но в любом случае это один.

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;
    }
}

Отражение с помощью этой функции разрешит только один переворот на каждый бит.