Большинство двоичных комбинаций из 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

Edit:

Хорошо, давайте повторим, что вы имеете в виду, а не то, что вы говорите.

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

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

Пример:

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

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

Answer 2

Вы хотите Серый код . Посмотрите на полпути вниз для "Построения n-битного серого кода".

Answer 3

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

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

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

111
110
100
000

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

Answer 4

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

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

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

Answer 5

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

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

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

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

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

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

Answer 6

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

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

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

Answer 7

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

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

Если вопрос «Сколько возможных последовательностей может быть сгенерировано?», То:

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

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

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

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

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

Answer 8

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

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

или, используя смены: (1 << i) - 1 для i в 0 .. </p>

Answer 9

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

Как:

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

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