Столкнулся с онлайн-тестом, есть некоторые непонятные для меня моменты в задаче.
Какие утверждения справедливы для последовательности чисел, генерируемой алгоритмом? (только один ответ)
for i = 0..2^k-1
output(i^(i>>1))
Где ^ - побитовый XOR
>> - сдвиг на один бит вправо
1. Следующее число всегда больше предыдущего
2. i-й бит следующего числа хранит сумму по модулю два всех битов предыдущего числа, номера чьих позиций меньше либо равны i.
b_i = ( \sum_{j=0} ^ {i} a_i ) % 2
3. Битовое представление следующего числа отличается от предыдущего только в одном бите.
4. Без первого элемента последовательность совпадает со следующей:
seq(2^k)
seq(2^k) = seq(2^{k-1}) 2^k seq seq(2^{k-1})
seq(1) = 1
Что я могу и уже сделал:
1. Взял некое k и получил последовательность промежуточных результатов, чтобы посмотреть. Это занимает большое время, очевидно тут надо работать не руками.
2. Понимаю, что такое xor
3. Понимаю, что сдвиг на один бит вправо даёт деление по модулю 2
4. Погуглил по синтаксису секвенций из ответов - не нашёл.
Мои вопросы:
1. Не понимаю синтаксис описанных секвенций, в гугле не нашёл, видимо не могу составить верный запрос по теме.
2. Не понимаю как быстро описать правило результирующей последовательности. Очевидно, что расписывать всю таблицу истинности для некоего k и искать потом закоомерность глазами - не то, что ожидается, учитывая, что на решение отводится минимум минут.
3. Видимо что-то не совсем знаю про свойства XOR в сочетании со сдвигом и вычитанием.
Помогите, пожалуйста, разобраться с принципом решения.
P.S. Я не хочу пройти тест за ваш счёт, в следующий раз вопросы всё равно будут другие. Моя задача - изучить тему и освоить подход.
Простой
